Seems to me that a simple solution would be people wanting a taxi bidding up the price. So if a taxi is two minutes from completing its current fare, people can start bidding on getting a taxi, and the moment this taxi is free, whoever has the highest bid will win it.

There really are no other workable solutions. The other solution is to get more taxis on the roads, but that would just mean that a lot of taxis would be idle at non-peak hours, and that -- instead of peak hour-taxis being expensive -- the price of taxis in general would rise, because each taxi isn't getting as many fares.