Hydrogen Fuel Cell and Battery
If you have a fuel cell, only hydrogen needs to be carried with the car; the air provides all the oxygen you need. Hydrogen is an extremely light fuel, but there are some issues with current means to contain it (e.g. heavy high pressure container, or massive hydride tanks).

According to Iceland is Bullish on Hydrogen, they've started to use their plentiful geothermal and hydroelectric power to electrolyze water, using the hydrogen to power cars and the oxygen byproduct for other uses.