How low does oxygen level have to be?
Altitude.org has a lot of information on oxygen levels in the blood stream at different altitudes. First, this page with charts shows the effects of 4000m altitude. 4000m is significant because this is about the highest that people regularly live at. There are very few permanent settlements above 4000m.
Oxygen partial pressure at sea level is about 21 kPa, corresponding with the 20% oxygen content in the air (since air pressure is about 101 kPa). At 4000m, oxygen partial pressure is 13 kPa, which means you only breather in about 60% as much oxygen in each breath at sea level.
This second page shows hemoglobin saturation plotted against oxygen partial pressure. At about 13 kPa partial pressure of oxygen saturation is still about 100%. At 8848m (the height of Everest), oxygen partial pressure is down to about 6.5 kPa. Looking at the hemoglobin saturation curve, hemoglobin saturation is down around 80 percent. I would consider a permanent year-round oxygen supply of 6.5 kPA to be fatal or close to it for most of the human population.
How to explain your problem
The shape of the hemoglobin saturation curve suggests a solution. If oxygen levels get into the part of the curve around the 4–6 kPa range, then most people on earth would die. However, that means that you need very little added oxygen to induce a significant improvement in your health.
Let us say that oxygen partial pressure is 5kPa in your depleted earth. Since nitrogen partial pressure would stay constant at about 80 kPa, and nitrogen and oxygen are about the same sized molecules, the air is roughly 60,000 ppm oxygen. In order to get people to survive, lets say you want 10 kPa oxygen partial pressure; that corresponds to about 110,000 ppm oxygen.
Now here comes the math. A person's tidal volume (the amount of air taken in each breath) is about 0.5 liters, so to increase oxygen concentration of each breath from 5 kPa to 10 kPa, takes 0.5 × (0.11 - 0.06) = 25 mL of oxygen for each breath. You take 14 breaths per minute, so that is 0.35L per minute. Oxygen has a density of 1.49 g/L; so now you need 0.5 grams of oxygen to breath for a minute.
12 gram CO₂ cartridges cost about 50 cents a pop; pretty cheap. They are also small and lightweight. One of those, filled with oxygen, will be enough to breathe with for 24 minutes at the above calculation.
Solution
A simple breathing mask, not gastight, but equipped with a valve designed to release a small amount of oxygen every time a breath is taken, with three 12 g cartridges plugged in would be lightweight (could be less than 1 lb), and provide enough oxygen for about an hour. A scuba tank has about 2180 liters of compressed air, and thus would provide about 100 hours of oxygen at the needed rate.
Because of the way the hemoglobin saturation curve is shaped, a small increase in oxygen can make a big difference between survival and death. If the world's oxygen levels are at one of the high slope parts of the curve, then a very modest oxygen supply can make a big difference.
Unfortunately...
This still won't work. If you are writing popular sci-fi (or a TV show) hand-waving the inconvenient truths is probably just fine, but the fundamental problem is: where does the oxygen go? If you want to drop oxygen partial pressure from 21 kPa to 5kPa, you have to remove about $7.5\times10^{17}$ kg of oxygen. That is a lot.
There is essentially no conceivable metabolic process for your oxygen-eating microbes that does not turn oxygen into carbon dioxide. The only other possible molecule that is likely to soak up so much oxygen is water. Unfortunately, water needs hydrogen to make it, so to convert a a lot of oxygen to water, you need something with tons of hydrogen and no carbon (otherwise carbon dioxide will form).
There is one substance I can think of that is common, and fits the bill: ammonia. So great! These microbes react ammonia and oxygen to make water (and nitrous oxide) and make energy! Except that there just isn't that much ammonia on earth. If we were to add that much ammonia to earth, that would represent a comet made of solid ammonia about 50km across. Since the dino-killing asteroid was about 10km, adding 50 km of ammonia will cause many more problems than lack of oxygen, such as vaporizing the oceans.
So really, the only way to get rid of oxygen is to turn it into Carbon Dioxide. But if we turn rougly 3/4 of the Earth's oxygen into Carbon Dioxide, then now the atmosphere is 15% CO₂ (or 150,000 ppm). This is a problem because a. I can't think of any animals bigger than bacteria that won't die of carbon dioxide poisoning, and b. if you think global warming is bad at the current 400 ppm, wait until you see 150,000 ppm.
I can't think of a solution to your 'remove oxygen without extinguishing life on earth' problem, but if I do I will let you know.