DNS changes does not provides high availability at all. Even with a ttl of 60 seconds, if a cache decides to overwrite your TTL, you're screwed.
Real high availability comes with a price: redundant datacenter with BGP failover.
While BGP is certainly better, the vast majority of DNS servers honor TTL nicely these days. In the old days, there used to be many problems, but I have been shocked at how well DNS failover has worked in the past few years.
How does that work? If you have a link explaining it a bit that would be great! (a Google search shows me all sorts of solutions for ISPs, but not for application hosting).