You are confusing free oxygen, O2, with oxygen in general. There was plenty of oxygen in the early Earth's atmosphere in the form of CO2 and other compounds, plenty of of oxygen in the early Earth's oceans in the form of H2O, and plenty of oxygen in the early Earth's crust in the form of many oxygenated compounds.