Europe is all GSM 900/1800 with some 3G 2100. Verizon is CDMA, none of their phones will work in Europe except some very overpriced ones that are CDMA/GSM hybrids. (My Cingular phone works great in Europe, except for the $1.29/min roaming rate.)
My advice would be to look for a used unlocked GSM phone on eBbay that is either 900/1800 or else triband 900/1800/1900 or 850/1800/1900. You should be able to get something like a Motorola V60 for no more than $30.
Once you get to the UK, drop by any Carphone Warehouse and get a prepaid Mobile World SIM. It costs 10 pounds and includes 10 pounds of airtime. Calls to UK numbers are 15p/min, to North America are a very low 5p, cheaper than anything else you are likely to find other than Skype. Inbound calls are free to you, paid by the caller. If you use up the 10 pounds, you can reload online or buy refill kits.
I haven't bought a SIM in Germany, but you should be able to get a prepaid SIM kit from Vodafone or T-Mobile at a newsstand for 20 euros or so with reasonable domestic rates, and again inbound calls are free to you, paid by the caller. (I say this based on SIMs bought in Luxembourg, Belgium, Switzerland, and France.)
The Mobile World SIM only works in the UK. You can get SIMs from other UK carriers that do roam in Germany but they cost more and the roaming rates are incredible both inbound and outbound, often $3 or $4/minute.
R's,
John