> Carbon doesn't really contain all that much hydrogen.

The hydrogen also comes from water reacted (mildly endothermically) with carbon, and by further reaction of carbon monoxide with water.

C + H2O --> CO + H2

CO + H2O --> CO2 + H2