Well, what cities do now is make parking the first n stories of a building, and then build the rest of the structure on top of that as normal. Over the last 5 years, I have watched many of the parking lots in my neighborhood become parking lots with condos on top (and retail stores below the parking).
This seems to be the best of all worlds -- the parking doesn't take anything away, it just makes the buildings 5 stories taller. Why anyone would drive their car in a major city, though, is beyond me.
Now if only the roads could be moved underground and replaced with parks (and a bicycle path); that would be really nice.