You need to check the experience of distributed networks like I2P or GNUnet. Maybe something like the GNU Name System?

Any decentralization of DNS leads to the use of DHT. But any implementation of DHT requires an initial download of data about the network nodes. This is always the bottleneck in such networks.