Most pay wifi services only block TCP and UDP.  I found some software that tunnels TCP over ICMP (i.e. pings).  I think I just might have to do this.  Give me a shout if you're traveling soon and want to try it out.

I can see myself now, using TCP over ICMP, curled up in an airport somewhere drinking RC and eating a moonpie.
(Note: the only part I am actually planning is the part with the RC and the moon pie - probably on my front porch)