There are reportedly about 14,000 medallions. At $1,000,000 a pop, it would not be too terrible to have a one-time buyout paid over several years as a compromise to ending the system.
Another way we might handle this is just to convince these people to cut their losses and default - the banks should have better weighed the risk of deregulation - and give the cabbies themselves reimbursement up to some fixed amount (under $10K) for the inconvenience of reregistering themselves with rideshares, or any livery cab companies.