Wirelessly posted (Mozilla/5.0 (iPhone; U; CPU iPhone OS 4_1 like Mac OS X; en-us) AppleWebKit/532.9 (KHTML, like Gecko) Version/4.0.5 Mobile/8B117 Safari/6531.22.7)
Like "Small White Car" said, storing your contacts outside of the iTunes backup is pretty simple.
I've used Yahoo and Gmail for this exact purpose. Just go to your phone in iTunes (connected by USB), and select "Info". Enable "Sync Contacts" and select what service you want to use. Enter username and password to that account and sync.
At this point, I'll often go to Gmail or Yahoo on the desktop to make sure that the contacts have been uploaded properly.
When you hook up the new phone, just repeat the process and sync. Sometimes I'll have to sync one more time.
This is also nice since it gives you an easy cloud backup of contacts should you ever loose your mind and decide to buy a non-Apple smartphone.
1.- Create a quick account on the app
2.- Press the button to back up your contacts
3.- Restore your iphone
4.- Reinstall the app on your restored iphone
5.- Open the app and login
6.- Press Synchronize
And as with Yahoo and Gmail, you have a "cloud" back up. I found Gmail and Yahoo a bit too much for what I needed (maybe I didn't understand how to make it work), because they synced all of my contacts from Gmail (E-mail addresses from persons I don"t need in my phone), which I didn't want. So I found the phonecopy version much better and easy to use. Choose what suits you best.
1.Connect your iPhone to the computer using the supplied USB cable; if you have a Wi-Fi connection, your iPhone does not require a connection. Launch iTunes if it does not launch automatically. The iTunes software displays your iPhone on the left panel under "Devices."
2.Select "Restore" from Summary tab.
3.Decline the option to make a backup by selecting "Don't Back Up."
4.Select "Restore" to confirm you wish to restore your iPhone. Your last backup, including restore contacts to your iPhone from backup. Your iPhone will re-start and display the Apple logo.
5.Follow the steps offered by the iOS Setup Assistance for iOS 6 and later to clear the "Connect to iTunes" message. For earlier versions, leave your iPhone connected via your USB or Wi-Fi until the message "iPhone is activated" appears.