Actually, even a non-genetically modified human can already breathe quite a range of gases beyond a simple Oxygen/Nitrogen mix. There are numerous breathing gases that are in use, in a wide array of applications such as sea diving, mountain climbing, hyperbaric chambers, and spacecraft. The main requirements are: the correct amount of oxygen (within a certain range), and a lack of toxicity. Usually, breathing gases will contain oxygen, and some form of inert gas or gasses, such as Nitrogen, Hydrogen, Helium, Neon, or Argon. Even pure oxygen can be used. However, not all of these gases are useful for deep sea diving, because some (like pure oxygen, argon, or nitrogen) will become more toxic under higher pressures.
Oxygen is necessary, however, for practically every reaction that occurs in the human body, but especially by the brain. If there is not enough oxygen, the brain will suffer Hypoxia. Initially, this will cause a sense of euphoria, and an inability to perform complex tasks, shortly followed by passing out, permanent brain damage, and eventually death. Compared to the brain, the rest of the body is relatively tolerant of lower oxygen levels, at least for a little while. But it's still a critical factor for life.
On the other hand, if the body cannot eliminate enough CO2 (perhaps because the atmosphere already contains a high concentration of it, or is too dense to fully exhale), then the CO2 will form carbonic acid in the blood. This causes Acidosis, where the blood becomes too acidic, and can lead from headaches, to sleepiness, to causing cellular damage, to a coma, and probably death.
If you want your human to survive in a low-oxygen environment, there's not really an easy way around this, short of a breathing apparatus. Someone mentioned the possibility of a biological rebreather. I'm not sure if that could actually work, but it's one semi-plausible solution. Or instead, you might find a way to slow his entire body metabolism down, and put him in a state of hibernation or cryostasis, but he won't be conscious. You could perhaps replace his brain with a miniaturized computer, but then instead of oxygen, you need power. And if you can upload his mind into a computer, why keep the rest of the body?
Addendum: To show how forgiving the human respiratory system can be, as long as it gets enough O2 and gets rid of CO2, there have been some partially-successful experiments that demonstrate the possibility of breathing an oxygenated liquid. This mode of breathing has been postulated in science fiction for deep-sea divers, or astronauts in high-acceleration spacecraft.