1) Namecoin - http://dot-bit.org/

2) Tor

3) I think 1 & 2 should solve this.

4) This probably isn't that difficult to implement on top of Tor.