I think Sprint and/or Clear's WiMax service would fit the bill if you will spend most of your time in large cities. I know Tynan has tricks up his sleeve on this one.

This is one issue I've been investigating too. My planned solution is two fold.

The first is a proper antenna to pickup wifi at a distance (even if you need to pay a small fee it's probably worth it): http://www.amazon.com/USB-Yagi-directional-Antenna-802-11n-2200mW/dp/B003LLS5JI/ref=sr_1_2?ie=UTF8&qid=1334248909&sr=8-2

Then there's 5gb of 4gb from tmobile's pre-paid: http://prepaid-phones.t-mobile.com/monthly-4g-plans

I intend to keep all of my heavy data access isolated to times when I'm on wifi and keep the cellular network usage as minimal as possible. I'm not sure how that'll work out.

Yeah, I use Clear... it's fast and unlimited. Coverage is pretty good, too, as it was one of the first 4G networks. It's only in fairly large cities though... nothing out on the road. For that you'll need 3G, too. I just tether off my phone in those cases.

Yeah, I got a Clear wifi hotspot for now, though at the house I'm renting the reception is awful. I suppose I can just find a place where it's not and park there...

FreedomPop has been getting some coverage in the news lately. http://techcrunch.com/2012/09/30/freedompop-opens-its-freemium-internet-service-to-the-masses-with-new-public-beta/ it's not unlimited data (you pay for overages), but their plans seem to be competitive. 

Their top plan is $29/mo and comes with:

Guaranteed 4GB per month
Extra data at 1MB for just $.01
Compare to similar Verizon plans for over 50% savings

I have one of those old Sprint SERO plans and get unlimited 4G data. But I thought Sprint still gave unlimited 4G regardless but does charge for 3G after 5 gb?

Sprint uses Clear for their WiMAX network and is upgrading to their own LTE network this next year.

Overall though, wimax kind of sucks. It cannot penetrate buildings as well so you have to be next to a window and even then the signal strength varies. In parts of large cities like SF, there's no signal at all. Then again, I've been in the suburbs of Atlanta and get an excellent connection. Maybe dropping my phone one too many times has nixed its strength though

Two solutions would be setting up a wifi antennae, getting a compatible wireless adapter, and using other people's WEP routers. Other solution would be creating a cellphone antennae to boost the signal, it's a bit more expensive though.

I'm typing this in a coffee shop in Berkeley right now because I couldn't find a 4G connection to save my life

The problem with Clear is that if you use a decent amount of data on their 4G network, they will throttle the hell out of you. Google the issue if you plan to use the hotspot a lot. Plus, sprint's network sucks compared to Verizon, lets just be honest.

So, it basically comes down to Unlimited data and throttled (which is what you will get if you root a Sprint/AT&T/etc phone for free tethering or with Clear), or paying for your data to have no throttling.

I chose the latter; I have a 20GB "Share Everything" plan on Verizon, sharing the 20GB pool between my iPad with 4G LTE/3G and my iPhone 4S. I use WiFi when I can (like at my condo or a coffee shop), but for the most part, I use Verizon to tether for my internet (at work, our office has a really annoying webfilter called "Websense" that blocks almost everything, so I pay for my own internet connection to tether to my laptop so I don't have to deal with bullshit). 

I actually don't even store any music on my iPhone anymore, I stream everything (music, video) from my Synology NFS server over Verizon's service to my phone/iPad/laptop (Synology makes awesome iOS/Android apps, such as DS Audio, DS Photo, etc), as well as streaming music from Pandora/di.fm/etc. Life in the cloud is great!

I'm very, very happy with the coverage and speed of Verizon 4G LTE. I frequently download faster than 20+ MBit via LTE, which is actually faster bandwidth than my AT&T FiOS fiber optic wired connection I have at home!

Brian,

You might want to check out http://www.millenicom.com/ I've heard they're good but in reading the info they might cap.

Never had coverage luck with Clear.
I use T-Mobile, and while their coverage is less than stellar (though vastly improving with 4G), the "no hassle" unlimited data (with throttle after XX GB) has been a godsend.  And you don't have to pay extra to officially tether it (for unofficial uses, look at the Android FoxFi app).

That being said, it's nothing like wifi...

Does anyone know about MetroPCS or the other small-bells?