DNS is geen ding om snel wijzigingen in te maken, dat wordt namelijk overal gecached.
Je zou het zo aan kunnen pakken, maar of dat voor het genoemde budget lukt weet ik niet:
* meerdere servers (VPS ofzo) waar je programma op draait
* iedere server heeft een DNS entry: server1.nogwat, server2.nogwat, server3.nogwat
* deze DNS beheer je zelf op meerdere nameservers
* zorg dat de nameservers in je "nogwat" record niet allemaal dezelfde tld hebben
* laat je client random connecten op domein basis met een van de servers uit je lijstje
* het onderling synchroniseren daar had je al wat voor