> Even simpler, looking at the user agent string.
This would catch a lot of false positives. For example, I use Atomic Web Browser on my iPad and iPhone - it lets me change my user agent string because some websites try to redirect you to a slimmed-down mobile version, and I might want to get to the full version of the website. So it is quite often that I actually change my user agent string to show desktop Safari instead of mobile.
I guess the marginally harder problem would be linking together the proxy with the authentication of the connecting user, to let authorized tethering users through. Perhaps they could use a different proxy via a different APN, or similar techniques.