So, I understand that human skin color is based on the distance from the equator, but would it be possible to evolve skin to be a non-natural color such as green, pink, blue, purple, ect? Perhaps if it would not be possible on Earth, would it be possible on another planet with a different climate? What gives skin pigment, anyway? Does blood alter the color of skin? Does our red blood make us look pink? I'm sorry, that's a bit off track. Help?
Skin colour in humans is affected by three main sources: blood, melanin, and the skin cells themselves.
In the absence of the first two, skin is generally a yellow-white colour; this is the least likely to change (assuming something close to normal human biology), but also the least important. It's not a particularly intense colour, so it's easy for other things to overpower it.
Human blood is primarily coloured by the hemoglobin in our red blood cells. This is based on ferrous iron (Fe2+), giving the classic red colour. There are other options here; changing some of the iron in the hemoglobin to ferric iron (Fe3+) makes the blood (and therefore skin) appear blueish - unfortunately it does that by making it less effective at transporting oxygen, so while this does occasionally happen in individuals, it is highly unlikely to ever become widespread in the population.
Moving to more exotic options, some other species use hemocyanin instead of hemoglobin, which gives them blue blood. In pale-skinned humans, this would lead to a blueish skin colour instead of the normal pink. Changing the oxygen-transporting molecule used in the bloodstream is a major change to bodily function, though; it would be plausible as a result of genetic engineering, but not natural evolution.
Finally, most 'normal' variation in human skin colouring is due to variations in melanin concentration. This is a pigment which essentially exists solely to colour skin, for the purpose of protecting us against damage from UV light. This is the most likely way that other skin colours would evolve - humans already have multiple forms of melanin with different colours (red/blonde/black hair all get their colour from it in one way or another), and similar chemicals in other species have different colours again (particularly relevant to the question is squid ink, which is coloured by melanin and is blue-black). It would be perfectly plausible for some group of humans to develop a different skin colour due to a change in how their melanocytes function - possibly due to a change in diet and/or environmental pressure, or possibly due to a random mutation.
Skin color in humans is normally determined by the concentration of the pigment melanin in the skin. The genes of albinos prevent the synthesis of melanin, which means that their skin itself contains no pigment. Thus, they are very pale, except where their blood shows through the skin, in which case they may appear pink.
People may develop blue skin through a variety of medical disorders, such as cyanosis. They may also become blue because they consume silver orally, by way of a quack medicine called "colloidal silver", whose effects are demonstrated in the picture linked below. Apparently, this condition is called "argyria".
Thus, perhaps some species could evolve the ability to consume silver to make their skin blue. The most obvious advantage for such an adaptation would be for camouflage, assuming that some part the species' environment (the sky?) is a similar color.
Most of the answers so far have concentrated on the biological processes that contribute to the our perception of skin colour.
An alternative approach might be to look at how the human eye might evolve to interpret optical light differently.
Our eyes and brains currently interpret a certain range of frequencies in the optical light spectrum as possessing colours. If our eyes were to evolve so that a gradual shift in the range of frequencies we perceive were to take place, then what we perceive as natural skin colour today could in the future be interpreted as blue.
When we are exposed to too much silver dust, or injest too much colloidal silver, our skin actually does turn blue - it's called argyrosis. I'm not completely sure of the medical implications of the condition, but apparently it damages the rods in your eyes, and your kidneys.
If you had a population of people that lived off a food source rich in silver (for whatever reasons) they would definitely be blue. Add a little bit of genetic resistance to the more damaging aspects of silver, and voilà! Blue (or purple) people! It's just like how pink flamingoes are only that colour because of their diet!
I may be wrong but I think plants have evolved to be green because green is the opposite colour to the light they receive from the sun. This means they absorb the most light possible.
As you didn't specify if the skin had to belong to a human, one could suppose that if an animal on a planet orbiting a red dwarf needed some way of converting its stars light to energy in its skin, their skin would be blue.