The end result was a gradual increase in oxygen levels

The short answers to "where did so much oxygen come from?" is: mostly from volcanos in the form of $\ce{CO2}$.

To understand this, we have to consider that the amount of atmospheric $\ce{CO2}$ is controlled by sources and sinks. At geological time scales the main source is volcanic activity and the main sink is silicate weathering. A key point to consider in this case the that the source is independent of $\ce{CO2}$ concentration while the sink is proportional to $\ce{CO2}$ concentration (and other factors like temperature or surface of exposed silicate rocks).

Therefore, if you have intense photosynthetic activity like the one described by @DavidHammen you can lower atmospheric $\ce{CO2}$ concentration, therefore reducing the intake by natural silicate weathering sinks, and at the same time increasing the atmospheric oxygen concentration. While this takes place, volcanoes keep putting $\ce{CO2}$ into the atmosphere and plants keep turning it into oxygen. If you keep this going on for a long enough time, you can rise oxygen levels as high as you want. Although, at some point other feedbacks will kick in to keep the oxygen level at bay. For example, wildfires will be more common and extensive in an oxygen-rich atmosphere, providing a stabilizing feedback that keeps a balance between $\ce{O2}$ and $\ce{CO2}$.

Effectively, plants in such scenario would have replaced part of the contribution of the weathering sink of $\ce{CO2}$. With the notable difference that the oxygen instead of getting washed to the deep ocean (and eventually subducted), was getting piled into the atmosphere as $\ce{O2}$, thus, slowly rising its atmospheric concentration.