The short answer is, $\ce{O2}$ is all around us!
You aren't breathing the $\ce{O2}$ that the trees next to you are respirating (at least not much). No matter which way the wind is blowing, you will have sufficient oxygen content. A "can't breathe" feeling comes from inhaling pollutants or extremely dry air (in which case you need to drink more water). Unless, of course, you are so far up in the atmosphere that there is simply less atmosphere to breathe (e.g. lower atmospheric pressure).
As you can see in the image below, the $\ce{O2}$ molecule abundance in the atmosphere is a giant reservoir that extends far up into the atmosphere. $\ce{O2}$ and $\ce{N2}$ are evenly mixed throughout the entire atmosphere, even beyond the stratosphere. Thus, the abundance of oxygen in the lower atmosphere is not really a local phenomenon.
Most of the free oxygen available is due to ancient oceanic phytoplankton, and they are still producing! While there are fluctuations in the oxygen abundance of the atmosphere on a geological time scale, there is no shortage of $\ce{O2}$ since there is an overwhelming amount of production.
For a quantitative breakdown of the oxygen production/consumption, see https://en.wikipedia.org/wiki/Oxygen_cycle

****Vertical profiles of the mixing ratios of selected species at the equinox****
R. M. Goody and Y.L. Yung, Atmospheric Radiation, Theoretical Basis, OUP, 1989.
This wikipedia article has a great discussion of the topic: https://en.wikipedia.org/wiki/Geological_history_of_oxygen
Before photosynthesis evolved, Earth's atmosphere had no free $\ce{O2}$. Photosynthetic prokaryotic organisms that produced $\ce{O2}$ as a waste product lived long before the first build-up of free oxygen in the atmosphere, perhaps as early as 3.5 billion years ago. The oxygen they produced would have been rapidly removed from the atmosphere by weathering of reducing minerals, most notably iron. This 'mass rusting' led to the deposition of iron oxide on the ocean floor, forming banded iron formations. Oxygen only began to persist in the atmosphere in small quantities about 50 million years before the start of the Great Oxygenation Event. This mass oxygenation of the atmosphere resulted in rapid buildup of free oxygen. At current rates of primary production, today's concentration of oxygen could be produced by photosynthetic organisms in 2,000 years.
Since the start of the Cambrian period, atmospheric oxygen concentrations have fluctuated between 15% and 35% of atmospheric volume. The maximum of 35% was reached towards the end of the Carboniferous period (about 300 million years ago), a peak which may have contributed to the large size of insects and amphibians at that time. Whilst human activities, such as the burning of fossil fuels, have an impact on relative carbon dioxide concentrations, their impact on the much larger concentration of oxygen is less significant.