[inquisitor]

Today nearly all GSM/UMTS phones (especially smartphones) sold in the US support quadband GSM, so in Europe voice telephony and smallband data will definitely work anyway. But when it comes to high speed data you need a phone supporting UMTS/HSPA at 2100 MHz, which is the only frequency band used for 3G in Germany while some other European countries have already deployed UMTS/HSPA to the 900 MHz band, too. So for Germany a 2100 MHz-capable 3G phone will do it.
In contrast AT&T run their 3G network at 850 and 1900 MHz and T-Mobile USA at 1700/2100 MHz (so-called "AWS"-band which is not compatible with the European UMTS 2100 MHz band as it uses different uplink frequencies).
AT&T and T-Mobile both sell phones that support at least UMTS 2100 besides their own frequencies, so you buy your phone from any of them. Just make sure it definitely supports UMTS 2100. Also be aware that some phones are sold with different frequency configurations throughout the world, so always check the specifications on the box!
For example the HTC Desire has been produced in three different versions:
900, 2100 MHz for Europe
850, 1900 MHz for North America (e.g. Telus Mobility Canada)
850, 2100 MHz for Telstra Australia

Or the Samsung Nexus S in two versions:
900, 1700/2100(AWS), 2100 MHz for Europe and T-Mobile USA
850, 1900, 2100 MHz for North American operators with UMTS 850 and UMTS 1900 networks like AT&T

The T-Mobile mytouch 4G supports the AWS-band (1700/2100) and the European 2100 MHz band as well as all global GSM frequncies (850/900/1800/1900 MHz), so it would work on T-Mobile USA and on all German networks.
By the way Lidl is way cheaper than Tchibo while giving absolutely the same service (both are on the O2 network).