By using a jailbreak program on the iPhone, I tethered for for several years. One month I downloaded a video through the tether, which clued AT&T in that I was tethering, because the video was too large for an iPhone. They sent me a polite letter sayin I could keep my current contract if I stopped tethering, or they would change my contract and eliminate my unlimited plan. I thanked them and told them I would stop tethering. Which I did.
Essentially , I'd you don't use their app but jailbreak the phone, they can't tell you're tethering unless you do something that triggers their suspicions - such as an large increase in usage, like I did.
Easier and faster is a portable hotspot like my sprint overdrive pro 4g. 50 bucks a month for 6 gb of usage - much more than I need, and it's the only wifi I have. Can tun 6 devices at one time if needed, and it establishes a local network between devices - even my printer for wireless printing.
With Linux, once the iPhone or hotspot is broadcasting, you just use the same program on Ubuntu as you would with any other wireless source.