Basically, on each phone set up two Apple IDs, one for iTunes purchases and one for iCloud stuff. The iTunes ID would be the same on both phones and the iCloud ID (MobileMe) would be different between the two.
For purchased items (apps, music, etc) you would both manually decide what you want on you own phone, but they would be from the same account (just as you previously used to sync via iTunes on your PC/Mac for both phones but with different configuration of apps and music. Then having your own iCloud/MobileMe on each phone will let you use all of the iCloud services distinct for each of you. So mail, contacts, calendars, iMessage conversations would be yours and yours alone.
Unfortunately, photos would sync under your iCloud/MobileMe account and not your iTunes account. I am not sure how you would share those or possible sync them between two accounts.
The other option, still involving separate iCloud/MobileMe and iTunes account would be to use the same ID for both of these on both devices. The only difference here is that the MobileMe info would then be the same on both devices, but you could create separate calendars and contacts lists for each of you. But email would be shared between both devices, iMessages would appear on both devices, etc. The upside is that you would have the same photostream on both devices.
Unlocked Pentaband iPhone 5 (AWS), unlocked iPhone 4
Unlimited airtime, Unlimited CAN/US long distance, Unlimited SMS to CAN/US wireless numbers
2500 Call Forwarding minutes to CAN/US numbers
Google Voice for visual voice mail with message transcription, conditional greetings, unlimited messages (vs 35 message cap), remote retrieval from any PC or phone, no auto-purge after 10 days and most importantly no $7-$8 charge.