In Germany I was able to buy a 20 euro a month data only plan for my iPhone and I was perfectly happy.
I ended up ordering the iPhone 5 on Verizon at the subsidized rate ($300) and stuck it on my dad's Verizon account for $30 a month (cheapest data plan only) and then when I go back to Germany later next year I'll just cancel it and try to get out of paying the early termination fee. Even if I have to pay the fee it's only $350 which, added with the initial price of the phone, is the same price as out-of-contract iPhone 5.
I'm considering picking up a Nexus 4, rather than bothering with rooting and re-imaging the Sensation. I don't really like the Sensation, though all the problems I have with it could be due to software. It's a custom build with Sense, which I really don't like.
Anyway, it's a new phenomenon. I was tethering on T-Mobile for years without trouble. About two months ago, they started shutting it down after a few minutes of use, and redirecting all traffic to their T-Mobile site upgrade page.