Yes, certain body parts can turn blue from a lack of oxygen. People's lips sometimes turns blue because when the light is diffused by skin, the veins appear blue.Look up cyanosis for a better answer.The blue color appears when veins are seen through the skin. The color of the vein wall itself, contrast, and translucency are what give the appearance of blue.
It is a widely repeated error, one that has even shown up in university instruction. Deoxygenated blood is a dark and unmistakable shade of red.
The entire iron complex (the iron center, the phorphyrin, the imidazole of a histidine residue, and oxygen if present) is responsible for the red color, and shifts in the geometry around the metal center affects just what the color is. When there's no oxygen bound the iron center has a distorted tetrahedral pyramidal geometry, with the iron sitting a bit off of the plane of the porphyrin. Once oxygen binds, however, the iron adopts an octahedral geometry, and sits directly in the plane of the porphyrine (it's probably how close to the plane of the porphyrin the iron is that has the biggest effect on the color, as even small changes in the electronics of the porphyrin, a massive chromophore, could create shifts in color; but this is just conjecture on my part). Carbon monoxide binding to the iron center has the exact same effect, but as CO has a much higher binding affinity for iron that oxygen a greater percentage of the hemoglobin becomes bound, resulting in the even brighter color.
As a side note, porphyrins not bound to a metal are often a dark purple or green to black color (and are an absolute pain in the ass to work with), so that may explain why the color of the heme complex becomes darker as the iron moves out of the plane of the porphyrin.