If I was looking for a cheap answer, I'd track down a GSM Galaxy Nexus. One Amazon vendor has it for $369. I'm assuming they can be had cheaper.

For the high-dollar set, hopefully the much rumored Google/Motorola X Phone will be coming out in December (just when my Verizon contract is expiring).