ATIV S can use wired tethering (search the forum for it, I posted instructions and drivers sometime last year). Even though my plan supports tethering, it's data-limited and when I use the wired tethering they don't list the data usage for it so I'm guessing it's not detectable, or at least not easily.
There's also an app called TetherX or something like that, which will act as a SOCKS proxy server on the phone; you then set your PC to use the phone as its proxy server. Won't work for non-proxy-aware apps but otherwise should do the trick.
Of course, this all assumes they're checking whether or not you're using the phone's tethering feature somehow, rather than doing something more nefarious like deep packet inspection. If they're checking "are you using the 'Internet Sharing' feature?" then I would expect them to just limit its usage; the phone has the capability to test whether or not tethering is permitted on your plan, and does so test by default. If they're using DPI and noticing traffic to/from PC clients (based on user-agent strings or something) then you're in trouble unless you can route all your traffic over SSL, which mostly thwarts packet inspection.