Full IPv4 tunneled through DNS[1] and even ICMP[2] has been possible for ages, and I've personally used ICMP-TX on an airliner to avoid paying for Wi-Fi (not because I'm cheap, mind, but because their registration didn't work).
For some reason those always crap out on me while OzymanDNS (the first major implementation in perl by dan kaminski) works pretty much every time, though it's quite different in operation.
To implement your own custom DNS server,
use Net::DNS::Nameserver; # (and see ozymandns for implementation example)
[1]: http://code.kryo.se/iodine/
[2]: http://thomer.com/icmptx/