ip over dns
this one is a given. if you have a caching dns server/forwarder, ip over dns like iodine or NSTX will usually provide you with a somewhat-unstable-but-probable internet access. the fix is of course to just tell dnsmasq to point all lookups by an unauthorized client to your http server and provide an http redirect to the paywall site. apparently this is ridiculously hard for admins to comprehend.
tunneling out through firewall pinholes
if admins set their firewalls up right, there should be no packets originating from an unauthorized wifi client which can hit a host on the internet. apparently it's much easier to just allow any wifi client to connect to udp port 53 on a remote host without even using a real dns service to pass along the query. openvpn listening on port 53 becomes highly useful here. a creative hacker could use something like a google voice-powered SMS-controlled app to report back any SYN packets in a 10-minute window and just try all 65k ports to find an open pinhole in a firewall.
ip over icmp
this one isn't nearly as likely to work as the last two, but when it does work it's much more stable a connection than ip over dns. examples are hans and ICMPTX. however it's usually rate limited to around 23kB/s in my experience (and it's probably much much much slower on IPv6, according to the spec only allowing something like 4 ICMP messages per second?), so if you can use a tunnel straight to a remote host without going through another protocol and its overhead, all the better.
overly permissive transparent squid proxy
so far i think i've only found one such proxy that successfully denies http requests to unauthorized users. people just don't seem to understand that even if your proxy doesn't have an IP address i can still use it. a very simple example is just doing
`echo -en "GET http://www.google.com/ HTTP/1.1\nHost: www.google.com\n\n" | nc www.google.com 80`. if this succeeds, their proxy is allowing anyone to just go right through to the internets without authing. to use this in practice download ProxyTunnel and use Dag's SSH-over-HTTP method to open an ssh tunnel with SOCKS5 proxy, or hell, a ppp-over-ssh tunnel to get Hulu to work. you should try both port 80 and 443 with this method as sometimes they'll only allow one outbound through the proxy. also take note that though the default transparent proxy might be too restrictive, you should scan the default route and the rest of the network with nmap for more open proxy ports like 3128, 8080, etc (hint: AT&T's open proxy port is non-standard). for the most part some variation on this ssh config line will get you what you want:
ProxyCommand proxytunnel -p www.google.com:80 -r remotehost:public_http_port -d remotehost:internal_ssh_port -H "User-Agent: Mozilla/4.0 (compatible; MSIE 6.0; Win32)\n"
MAC address/IP address cloning
this is probably the easiest/most reliable method to get through a paywall. if someone else is already authed, just sniff the network, find their MAC and IP address, set it as your own, and start browsing. to be honest i don't ever use this method but it should work in theory. if they enforce WPA encryption it should make this method difficult to impossible, though i'm really not up to speed on all WPA attacks.