There are typically two ways to implement high availability/scalability failover solutions. The first one is to use short TTLs on a round robin DNS record, in conjunction with a load balancer, and the second is to use heartbeat monitoring and IP address failover with a hardware or software solution. Some solutions use a combination of these two approaches for additional reliability.
Not saying you should plunk down cash to do this, but check out Zeus' ZXTM and GLB solutions to get an idea of what is possible with a commercial solution. I've used them in the past with my own hardware, and with good results.
FWIW, You should be able to be fairly reliable by using short TTLs in your DNS records, and then programmatically pointing the DNS at a backup webhead if you lose the LB. You can use a service like Zerigo to do this, as they provide an API you can hit to change your records on the fly. If you are looking to optimize on cost, this is the way to roll.
There appear to be a few solutions for doing this with Linux, including a solution built on top of LVS: http://www.cyberciti.biz/faq/rhel-centos-fedora-keepalived-lvs-cluster-configuration/, but there may be limitations on where you can deploy it (like not on AWS) and additional costs of setting it up, monitoring it, and getting it implemented correctly.