Fast, Reliable, Cheap. Pick any two.
Honestly, though, "zero downtime" is, for all intents and purposes impossible. You're wanting zero downtime, but it doesn't appear that you're willing to spend the money necessary to do it.
I believe you're on the right track with heartbeat and swinging the front end's IP to another node. Anything more involved than that would either involve contracting the services of a CDN like Akamai or Limelight or alternatively, obtaining an AS number, configuring BGP, getting an IP allocation, setting up gear in two geographically-distant colos and replicating data between them. Either of those options would be quite expensive and complex to implement.
What you're proposing is workable; it sounds like you're essentially recreating the architecture which eins.de used for their Ruby On Rails install for a while.
But, that said, it would not be my first choice. Why bother with load balancing and add/remove servers over FastCGI, when HTTP is so ubiquitous as it is? Which benefit do you believe you will gain from using FastCGI instead of HTTP?
I would just use an HTTP/HTTPS load balancer as first server, and then speak HTTP to the application server layer. And the application servers could use Apache2+mod_wsgi+Django or gunicorn+Django based on your preference.
There are many good HTTP load balancers available. Search through this site. Some common open-source choices are Perlbal, nginx, HAProxy & Apache 2.2 (in no particular order). There are also commercial appliances like Coyote Point, Loadbalancer.org, or services like Amazon ELB for EC2.
I am most concerned about ability to add and remove servers on-the-fly.
That's a good point, both about taking app servers out of service as well as completely reloading the load balancer config on the fly. Off the top of my head Perlbal, nginx and HAProxy can all reload their config file while running; but I'm haven't verified this just now.
Best Answer
Multiple options / solutions come to my mind:
NFS:
DRBD aka Distributed Replicated Block Device:
csync2:
There are other options available as well, just take this as a starting point.