Well an actual DNS server, Whats wrong with authoritative DNS? just use DNS NOTIFY to update slaves on record change.

That way TTL is not a problem, unless you have SSSD or nslcd doing caching on the client.

It'll remove a massive layer of complication, and will mean that you can have redundant service discovery even if your ETCD/skydns fails.

It'll certainly scale much, much higher than skydns. if you don't want to create your own DNS, Use Dyn. It has a REST interface, a very nice SLA. if you query the servers directly you also don't have to worry about TTLs