No need to upgrade your old iPhone to iOS4, you can leave it at iOS3.x.
You'll actually be restoring your info from your iTunes backup so (as long as you have iTunes version 9.2) you'll be fine. Your new iPhone will have iOS4 pre-installed, so just activate, restore and you'll be good to go.