Short term, at least, it's true that you're only going to have a lot of luck changing behavior with respect to car usage whene people do have other realistic options. I'm not sure how an urban gas tax makes any sense, as it just seems to punish people who have mostly already reduced their relative car use.
But, there are things which can be done. One is to reduce the subsidization of parking, whether by reducing below market municipal lots or ending the subsidization of employee parking. When companies provide free parking for employees they're giving them something of value which is both free from the perspective of the employee and tax deductible from the perspective of the company. You can improve the incentives a bit by handing every employee the equivalent of the implicit rent on that real estate every month and letting them use that money to either "rent" a parking space or they can pocket it or use it to by a train pass or whatever.
You can do what London has done and have a daily driving fee in the central city. That has actually reduced traffic quite a bit there.
Longer term, aside from improving CAFE standards the real way to reduce gasoline usage is to increase proportion of households for which "one car per driving-age member" is not effectively a requirement.
It'll be interesting to see what happens to Los Angeles. It's really a special case for a variety of reasons, and it actually wouldn't take all that much to reduce the car dependency (though not necessarily the car usage) of a hefty chunk of the population.
