I'd replace the free parking with great public transport and cycling infrastructure. The parking spaces can be in the surrounding area, with frequent public transport between them and the centre.

Look at European cities that have implemented this even in part, and tell me it isn't much nicer with fewer cars. Shopkeepers are usually opposed to it before, but see that the improvement in atmosphere attracts more customers than are lost through the lack of parking spaces.