The atmosphere of the Earth is mainly composed of nitrogen (N2, 78%) and oxygen (O2, 21%) molecules, which together make up about 99% of its total volume. The remaining 1% contains all sorts of other stuff like argon, water and carbon dioxide, but let's ignore those for now.
As you probably know, the oxygen we breathe is produced by plants from water and carbon dioxide as a byproduct of photosynthesis. Conversely, animals (including humans) use the oxygen to burn organic compounds (like sugars, fats and proteins) back into water and carbon dioxide, obtaining energy in the process. So do many bacteria and fungi, too, and some oxygen also gets burned in abiotic processes like wildfires and the oxidization of minerals.
The result is that oxygen cycles pretty rapidly in and out of the atmosphere. According to the Wikipedia article I just linked to, the average time an oxygen molecule spends in the atmosphere before being burned or otherwise removed from the air is around 4,500 years.
The most recent known Homo erectus fossil dates from about 143,000 years ago, so the probability that a particular oxygen molecule hitting your face today has been around since that time is roughly $\exp(- 143000 / 4500) = \exp(-31.78) \approx 1.58 \times 10^{-14}$, i.e. basically zero.
Of course, the oxygen atoms used for respiration don't disappear anywhere: they just become part of the water and carbon dioxide molecules. Those that end up in carbon dioxide usually get photosynthesized back into free oxygen pretty soon, unless they happen to get trapped in a carbonate sediment or something like that. The oxygen atoms that end up in water, on the other hand, may spend quite a long time in the oceans before being recycled back into the air; if I'm not mistaken, the total amount of oxygen in the hydrosphere is about 1000 times the amount in the atmosphere, so the mean cycle time should also be about 1000 times longer. Still, eventually, even the oxygen in the oceans gets cycled back into the atmosphere. Thus, while the oxygen molecules you breathe might not have been around for more than a few thousand years, the atoms they consist of have been around since long before the dinosaurs.
How about nitrogen, then? Perhaps a bit surprisingly, given how inert nitrogen generally is, it's also actively cycled by the biosphere. Unfortunately, the actual rate at which this cycling occurs seems to be still poorly understood, which makes estimating the mean cycle times difficult.
If I'm reading these tables correctly, the annual (natural) nitrogen flux in and out of the atmosphere is estimated to be somewhere between 40 and 400 teragrams per year, while the total atmospheric nitrogen content is about 4 zettagrams.
This would put the mean lifetime of a nitrogen molecule in the atmosphere somewhere between 10 million and 100 million years, well above the time since Homo erectus first appeared (about 1.8 million years ago). Thus, it seems that most of the air molecules around you have probably been around since the days of Homo erectus, and some of them might even have been present during the age of the dinosaurs, which ended about 66 million years ago.
The sky does not skip over the green range of frequencies. The sky is green. Remove the scattered light from the Sun and the Moon and even the starlight, if you so wish, and you'll be left with something called airglow (check out the link, it's awesome, great pics, and nice explanation).
Because the link does such a good job explaining airglow, I'll skip the nitty gritty.
So you might be thinking, "Jim, you half-insane ceiling fan, everybody knows that the night sky is black!" Well, you're only half right. The night sky isn't black. The link above explains the science of it, but if that's not good enough, try to remember back to a time when you might have been out in the countryside. No bright city lights, just the night sky and trees. Now when you look at the horizon, can you see the trees? Yes, they're black silhouettes against the night sky. But how could you see black against black? The night sky isn't black. It's green thanks to airglow (or, if you're near a city, orange thanks to light pollution).
Stop, it's picture time. Here's an above the atmosphere view of the night sky from Wikipedia:
And one from the link I posted, just in case you didn't check it out:
See, don't be worried about green. The sky gets around to being green all the time.
Best Answer
Nope! The blue sky comes from Rayleigh scattering through air, but pretty much any gas whose molecules are decently polarizable will work equally well - it doesn't have to be oxygen. I suspect the guy probably said that there was very little atmosphere and atmosphere is what makes the sky blue (although does it really count as a "sky" if there's no atmosphere?...) and the reporter misunderstood.