>Part of me thinks Uber could get away with this if they just relaxed some of their current driver policies (e.g. more limited penalties for cancellations). The issue is whether doing so would drastically deteriorate the quality of the service for riders.

Honestly, just keep the 'we don't show drivers with a less than X star rating' in place, and allow the rider to give the driver a low rating for cancelling. Self correcting problem - drivers that routinely cancel will be pushed out, and the (potential) one bad rating shouldn't hurt routinely good drivers.