I tether data using WiFi out of my Nexus devices regularly. Your phone company is restricting it. I am kinda feeling bad for you though as you took so much effort to type out a large rant.
Have you been able to tether using a Nexus 7? Can you kindly provide a screen shot of the 'tethering and wifi hotspot' settings screen from the latest Android on a Nexus 7. Will appreciate it.
Don't feel bad. A lot of good had come out for me via HN :)
I use a Galaxy Nexus and a Nexus 4. I am a little surprised that a device with the exact same OS version doesn't have this, and I have seen it almost all other android tablets. I guess I made the wrong assumption. Sorry.