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:
When the minifigure first appeared, it was decided that its face should have only one colour: yellow. And that its facial features should be happy and neutral . The figure would have no sex, race or role – these would be determined by the child’s imagination and play.
It then explains when and why they added colour for their licensed figures
With licensed products such as LEGO® Star Wars™ and LEGO® Harry Potter™ the figure began appearing in specific roles, and with LEGO Basketball in 2003 it took on authentic skin colours. In 2004 the LEGO minifigure assumed an even wider range of skin colours when it was decided that the figures in licensed products should resemble the original characters as closely as possible. One result was that the figures in LEGO Harry Potter™ changed from yellow to a more authentic skin colour.
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. The first Star Wars set in 2004 with flesh-toned figures was the Millennium Falcon. By 2005 the transition for Star Wars was complete and all sets used flesh-toned figures.
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:
Page 59, sentence 2: Originally, the LEGO Group sought to leave racial and gender differences to the imagination of builders by using a stylised, generic face with outfits to differentiate roles.
Page 59, sentence 4: The most noticeable feature of the majority of mini-figs is
their ostensibly "race-neutral" yellow coloration. The paradigm lasted until 2003, when LEGO Sports' Basketball theme was released, featuring minifigs based on real-life NBA players. The LEGO Group decided that expecting kids to appreciate figures that didn't really resemble the stars they represented was a losing proposition.
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.