1. Fill a lobby up based on location and ping, like it currently does.
2. Determine the exact average k/d ratio for the lobby.
3. Balance the teams out so that each team is as close to the lobby k/d ratio as possible.
This way, games wouldn't be any more or less difficult to get into than they currently are, but each game should be less likely to have one team just dominate. It also would avoid encouraging people to somehow "game" the system, since there would be no advantage to doing so.
They have all the stats they need for it already, and implementing such an algorith would hardly tax even the most basic of computers, much less servers.