Depends on your carrier. Depends on what you mean by "cheap" (paying up front, subsidized, etc.).

My gf just got a refurb iPhone for $50. But that's subsidized, locked, and on AT&T. And it's an iPhone.

You could probably find a Mytouch 3G or G1 on ebay for cheap-ish, if you want T-Mobile.