What if life figured out how to use oxygen before it was freely available?

Did the production of oxygen coincide with the "Great Oxygenation Event", or did living organisms have access to oxygen even before that event?

Moon and Earth’s Atmosphere (photo credit: NASA)
Moon and Earth’s Atmosphere
(photo credit: NASA)
Around 2.5 billion years ago, our planet experienced what was possibly the greatest change in its history: molecular oxygen suddenly went from nonexistent to becoming freely available everywhere. 
While it is a fact that the “great oxygenation event” (GOE) occurred, allowing oxygen-using organisms – also called the "respirators" – to evolve, one question still remains. This is what  Prof. Dan Tawfik of the Weizmann Institute of Science’s Biomolecular Sciences Department set out resolve. 
The question being whether this event actually radically changed the way oxygen-using organisms breathed - or were they using oxygen at the time already using free oxygen, just at lower levels? Did the production of oxygen coincide with the GOE, or did living organisms have access to oxygen even before that event? 
On one hand, according to the study, molecular oxygen would not have been available before the GOE, as the chemistry of the atmosphere and oceans prior to that time would have ensured that any oxygen released by photosynthesis would have immediately reacted chemically. 
But on another hand, however, some of the oxygen produced by the photosynthetic microorganisms may have remained free long enough for non-photosynthetic organisms to snap it up for their own use, even before the GOE. 
Part of Tawfik’s research team, Jagoda Jabłońska thought that focusing on the protein evolution could help resolve the issueThat is, using methods of tracing how and when various proteins have evolved, she and Tawfik might find out when living organisms began to process oxygen.
Such phylogenetic trees are widely used to unravel the history of species, or human families, but also of protein families, and Jabłońska decided to use a similar approach to unearth the evolution of oxygen-based enzymes.
“Of course, it was far from simple,” said Tawfik. “Genes can be lost in some organisms, giving the impression they evolved later in members in which they held on. And microorganisms share genes horizontally, messing up the phylogenetic trees and leading to an overestimation of the enzyme’s age. We had to correct for the latter, especially.”
The phylogenetic trees the researchers ultimately obtained showed a burst of oxygen-based enzyme evolution about 3 billion years ago – something around half a billion years before the GOE. 
Examining this time frame further, the scientists found that rather than coinciding with the takeover of atmospheric oxygen, this burst dated to the time that bacteria left the oceans and began to colonize the land. A few oxygen-using enzymes could be traced back even farther. 
"This confirms the hypothesis that oxygen appeared and persisted in the biosphere well before the GOE," said Tawfik. "It took time to achieve the higher GOE level, but by then oxygen was widely known in the biosphere.”
If oxygen use had coincided with the GOE, the enzymes that use it would have evolved later, so the findings supported the scenario in which oxygen was already known to many life forms by the time the GOE took place.
“Our research presents a completely new means of dating oxygen emergence, and one that helps us understand how life as we know it now evolved.”