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.
In terms of other colours, LEGO had already created various monster and alien figures with different coloured heads ranging from blues and greys through to transparent and even transparent neon orange.
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.
The yellow head was originally used to represent all races and both genders. Later, yellow heads were used to represent non-licensed minifigures, and flesh coloured minifigures were used to represent licensed minifigures, such as Batman, or Indiana Jones, but flesh coloured minifigures weren't used until around the late 1990s.