Yep. Can't see any other way than unlocked, unbranded phone with pre-pay card. Bite the bullet & buy the handset. Do your homework first so that you get something that lasts AT LEAST three years or more, preferably something that is easy to rom upgrade (thanks, android).
Re: tethering. This is something most people will only do infrequently, in the hotel or train, if they've forgotten their dongle or MiFi. In fact it's good to have a MiFi aswell, then you get a choice of operators if signal is an issue.
I'm pretty sure networks are not monitoring people for tethering. There must be software that detects heavy usage, like when connections are open longer than normal, & heavy data usage. I've received text warnings when watching youtube clips too much (no tethering involved), & that was on a so-called "unlimited" data tariff. So you can tether, but don't hog it so much that they notice!