Yeah, you want leastconn + app/router affinity. Affinity is the statement that all of your requests for an app go through one router (to avoid distributed connection state tracking).

In the past, I've accomplished this by having the next layer up consistent hash the api keys onto the router list. If you don't control the top layer (ELB), you need to add a dumb layer just for the hashing.

HAProxy works great for this extra layer. In practice, all you end up doing is adding a "balance hdr(host)" directive (see http://haproxy.1wt.eu/download/1.5/doc/configuration.txt) to get the hashing right, and you're spending <1ms inside HAProxy.