A significant "gas guzzler" tax on new energy-inefficient vehicles would help, but only if it were truly significant. Backing that up with a recurring licensing/registration tax would also be helpful, but doing that on a region-specific basis would just push people to renew their licenses out of town. But to work, a carbon tax needs to go on all fossil fuel uses, not just transportation. Stuff that costs more energy/CO2/emissions to make, transport, dispose etc. SHOULD cost more to buy. Do this, and consumption patterns WILL change because costs WILL increase. Imports would need to be tarrifed/taxed to make sure that they compete on the same playing field even if they choose not to tax their energy inputs.
I disagree that a fuel tax is "regressive". It isn't "progressive" either- it's a "flat" tax, in that it charges people on the basis of their use rather than their ability to pay. But if you build your income tax system correctly and progressively, flat taxes on consumption aren't regressive. They merely promote conservation and punish waste.
In regard to the cost of fuel and its feedback into purchasing decisions: that's an easy one. Increase taxes gradually until you see the desired effect. Will tax eliminate Escalade- and Hummer-driving morons from our streets? No. Choices will remain free to those who can afford the full and fair cost of those choices, and there's no law against being an idiot. For all we know, they live in superinsulated or earth-sheltered passive annual heat storage houses and can afford the extra fuel because they spend nothing on heating and cooling. Or maybe they're just fabulously wealthy and don't give a rat's @ss about the 'plebes. Won't matter- they'll be in the minority.
As to the carrots (incentives, subsidies etc.), they are paid for by the stick (tax), and they can be enormously progressive- or flat, your choice. A transit subsidy, by its nature, is progressive in that more poor people than rich people use public transit because they have no choice. Road subsidy could be argued to be regressive, since only those who can afford to buy, license, insure, maintain and fuel vehicles get to benefit directly from road investment. And they suffer indirectly as a result of the emissions etc.
UcfSE: this board is a forum for debate. I post frequently and argue passionately because I feel passionately about these issues and feel it's an important debate amongst my peers. I respect the points of view of many here whose opinions are diametrically opposed to my own, provided they can defend them when challenged. And it's an on-line forum, man- nobody is waiting in the background with their hand raised, waiting for the moderator to give them a turn to speak. If you have something to contribute to the debate besides taking issue with the opinions of others, then by all means contribute!