I was right. I went home and found out about some software called Iodine: http://code.kryo.se/iodine/
I was already using port 53 for authorative DNS on my VPS, so I spun up another server. I launched iodined. Then, iodine from the laptop. And, with some tweaking, it worked! I used this setup with the occasional option change for a couple years. There's numerous Starbucks, airport, and -Guest networks which this works on. I even found a case where it would have worked on a free wireless network, where somehow the router did not route properly, except to the resolvers.
I'd always wanted to offer this as a service and finally had the chance to wrap it up. It's currently 398 lines of C and Bash to handle registration, payment via Bitcoin, and authentication all over SSH.
I would really appreciate it if you guys played around with it. It hasn't seen a single user yet, and even if it doesn't take off it'd mean a lot to me to see it in action.
Let me know if you have any questions about the site or tunneling via DNS/raw UDP traffic. I haven't jumped into all of the specifics that much, but have a decent grasp of what's going. I know there are some better explanations of DNS tunneling out there and there's also a Perl daemon that does it, and probably more. And apologies for the ugly site. I'm dating a girl with a graphics design background, so perhaps that will change some time