When did the flesh colors start and why? It seems yellow heads are here to stay too?
To answer the first part of the question, the Company Profile presentation (deep, direct link) states:
It then explains when and why they added colour for their licensed figures
The first ones I remember seeing were indeed some of the NBA League characters as part of the Basketball theme in 2003, followed by the Star Wars products and then the Harry Potter sets in 2004.
Lando Calrissian was one of the first to appear in the correct skin tone, amongst yellow Han and Leia:
Followed later by pink characters for the rest.
Since then, the collectable Minifigures have occasionally featured non-yellow heads for some of their more "monstrous" figures, such as the Witch, Zombie and genie.
The Cult Of Lego book (ISBN: 978-1-59327-391-0) had an a whole page about the change in minifigure skin colour:
Since the NBA figures were released in 2003, beige and brown skin tones have been used only in licensed sets to portray characters. Traditional LEGO themes like Police and Firefighters continue to use a yellow flesh colour.
The distinction between skin tones makes it easy to identify a beige or brown minifigure as part of a licensed set. Licensed sets tend to be based on film and television themes.