In the US people will have a huge fit if you attempt to "discourage new car sales" by adding a, gasp, tax to them.  That's all anyone will hear.  Remember, Americans are idiots.

The above idea of subsidizing trade-ins and giving people a break on the "loss" is a great idea because it doesn't cost much and makes people think they're getting something for free.  I'd also suggest that controlling the size of auto loans is a good idea too, but that's also sacrilegious.

If you want to be genuinely progressive you'll find a way to funnel a substantial amount of money into public transit during a gas-guzzler trade-in program.  If you can generate a billion or two dollars in any given metro area you can seriously jumpstart mass-transit infrastructure.