Use HAProxy. Take the time to configure it correctly. It's absolutely the most stable and useful loadbalancer I've used. It also solves this issue by talking to your backends.
I would highly recommend keepalived, which is well-written software for managing ipvs, a load balancer in the Linux kernel. Very, very fast, flexible, and extremely reliable.
EDIT: ipvs/keepalived only operate at layer 3, which is one reason why they are so fast. if you need layer 7 stuff, this won't do it.
We use pen, which can be configured to avoid this issue as well. Just specify the maximum number of connections to be the same as the number of backend servers (via the -x option), and it will queue connections beyond that number and hand them to the first backend that frees up.
We've had zero issues with pen, it's been rock solid, but we're still looking at moving to Passenger at some point: seems like it will be more flexible and efficient than our current pack of mongrels.
I attempted to switch to pen when I was having issues with Perlbal. It was segfaulting under light load (light for me is heavy for most people) comparable to Perlbal, so I switched back. I can't say I reccomend it at all.
EDIT: ipvs/keepalived only operate at layer 3, which is one reason why they are so fast. if you need layer 7 stuff, this won't do it.