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).
To implement your own custom DNS server, use Net::DNS::Nameserver; # (and see ozymandns for implementation example)