I haven't though about this carefully but I wonder what the shortcomings of the following would be: when a domain 'owner' wants to update their DNS entry, they just push out a PGP-signed (or similar) message of their new IP onto a P2P swarm, which will only propagate your message if their message verifies with their public key, from which you can then grab the entry (and verify it again for extra security). Then, registering your domain would just consist of getting the swarm to accept your public key. Of course, this could be first-come first-serve, or it could be regulated in some way. This way you could have multiple swarms, and each swarm is only governed by their own decisions.

And I suppose on a smaller scale, TPB could create their own swarm right away, and have people use it parallel to existing DNS infrastructure. Then other censored domains could jump onto their swarm.