If you decide to go with Verizon, you can temporarily enable their International service at quite reasonable cost and have a totally seamless experience which only requires that you reboot your phone when you land in Europe and again when you land in the US. They have a couple of plans - one is like $10 for any 24 hour period and only kicks in when you actually use the phone, the other is something like $40 per week. I have several international travelers at my office, all on Verizon iPhones, and these plans work very well for them. Honestly, plans may be different for non-business customers - I don't know.
Otherwise, make sure whatever phone you end up with will be unlocked and allow use of SIMs from other carriers. Then, when you are in country, just find a local cell store and inquire as to the best SIM/plan for your needs. You'll find many very good deals, but, of course, you will have only a local phone number for the duration.