Changing color in beamer header (Singapore)

Question

I am not a TeX-pert and I basically spent half the day trying to figure out the following change to the Singapore theme of beamer.

What I want is to give every sub part (section) a different color in the header. I got so far as to change the color of the shading in the header (see picture).

However, what I additionally want, and don't manage to accomplish, is that the parts "Introduction", "Overview", ... have a different background color (while the color of the shading stays the same). What I have in mind is that the background of the section titles each have a different color and when I am in that section, the shading changes to that particular color.

I don't mind if it is not a fully automated solution, but something handcrafted. Any help is greatly appreciated.

Edit Upon request, here's the way how I changed the color of the shading. I basically defined a new command which I call after each section command.

\newcommand{\changecolor}[1]{
  \setbeamercolor{title}{fg=black}
  \setbeamercolor{frametitle}{fg=black}
  \pgfdeclareverticalshading{beamer@headfade}{\paperwidth}
  {
    color(0cm)=(section in head/foot.bg);%
    color(.95cm)=(#1)
  } 
}

Edit 2 In order to not cause unnecessary effort, here's a very cheap gimp'ed version of my desired result.

Answer 1

Now I made a significant simplification to my initial solution. In the code below I used a green-based color scheme, but redefining appropriately color0, color1,..., color7, the colors can be customized. I also added a little (optional) decoration at the bottom right corner of the frames:

\documentclass{beamer}
\usepackage{totcount}
\usepackage{tikz}

\regtotcounter{section}

\definecolor{color0}{HTML}{00675E}

\definecolor{color1}{HTML}{00B366}
\definecolor{color2}{HTML}{34CFCB}
\definecolor{color3}{HTML}{007D48}
\definecolor{color4}{HTML}{80FFC9}
\definecolor{color5}{HTML}{5DCFC3}
\definecolor{color6}{HTML}{BFFFE4}
\definecolor{color7}{HTML}{009E8E}

\makeatletter

\def\sectioncolor{color0}% color to be applied to section headers

\setbeamercolor{palette primary}{use=structure,fg=structure.fg}
\setbeamercolor{palette secondary}{use=structure,fg=structure.fg!75!black}
\setbeamercolor{palette tertiary}{use=structure,fg=structure.fg!50!black}
\setbeamercolor{palette quaternary}{fg=black}

\setbeamercolor{local structure}{fg=color0}
\setbeamercolor{structure}{fg=color0}
\setbeamercolor{title}{fg=color0}
\setbeamercolor{section in head/foot}{fg=black}

\setbeamercolor{normal text}{fg=black,bg=white}
\setbeamercolor{block title alerted}{fg=red}
\setbeamercolor{block title example}{fg=color0}

% Each \section redefines \sectioncolor and applies the shading with this color
% add as many colors as you need
\AtBeginSection{%
  \renewcommand\sectioncolor{%
    \ifcase\value{section} color0\or color1\or color2\or color3\or color4\or color5\else color6\fi}
  \setbeamercolor{frametitle}{fg=black}%
  \pgfdeclareverticalshading{beamer@headfade}{\paperwidth}
  {%
    color(0.25cm)=(bg);
    color(1.25cm)=(\sectioncolor)%
  }
}

\newlength\sectionboxwd

\AtBeginDocument{%
  \ifnum\totvalue{section}>0 
    \setlength\sectionboxwd{\dimexpr\paperwidth/\totvalue{section}\relax}
  \else
    \setlength\sectionboxwd{\paperwidth}
  \fi
} 

\newcommand\insertcolors{%
  \ifnum\totvalue{section}>0
    \setlength\fboxsep{0pt}%
    \foreach \x in {1,...,\totvalue{section}}
    {\colorbox{color\x}{\phantom{\rule{\dimexpr\the\sectionboxwd\relax}{5ex}}}}%
  \else\fi
}

\setbeamertemplate{section in head/foot}{\setlength\fboxsep{0pt}\hspace{-1.875ex}%
    \parbox[c][4ex][t]{\sectionboxwd}{%
      \hfill\parbox{\dimexpr\sectionboxwd-8pt\relax}{%
      \raggedright\insertsectionhead%
      }\hfill\mbox{}%
    }%
}

\setbeamertemplate{headline}
{%
  \begin{beamercolorbox}[wd=\paperwidth]{section in head/foot}
    \insertcolors%
    \vskip-4ex%
    \insertsectionnavigationhorizontal{\paperwidth}{\hskip-1.875ex}{\hskip-8pt}\vskip2pt
  \end{beamercolorbox}%
}


\pgfdeclareverticalshading{beamer@headfade}{\paperwidth}
{%
  color(0.25cm)=(bg);
  color(1.25cm)=(color7)%
}

\addtoheadtemplate{}{\pgfuseshading{beamer@headfade}\vskip-1.25cm}

\setbeamertemplate{navigation symbols}{}
\addtobeamertemplate{footline}{}{%
  \hfill\color{\sectioncolor}\rule[0.5cm]{2.5cm}{1pt}\rule[0.5cm]{1pt}{1cm}\hspace*{0.5cm}}

\title{A Beamer Theme}
\subtitle{With colorful headline}
\author{Gonzalo Medina}
\institute{\texttt{tex,stackexchange.com}}
\date{\today}

\begin{document}

\begin{frame}
\maketitle
\end{frame}

\section{Test section}

\begin{frame}
\begin{enumerate}
\item Test
\end{enumerate}
\end{frame}

\section{A test section with a really really long title}

\begin{frame}
\begin{enumerate}
\item Test
\end{enumerate}
\end{frame}

\section{Another test section}

\begin{frame}
\begin{enumerate}
\item Test
\end{enumerate}
\end{frame}

\section{Another test section with a really really long title}

\begin{frame}
\begin{enumerate}
\item Test
\end{enumerate}
\end{frame}

\end{document}

And some images, showing the titlepage and the first frame of every section in the example; the images illustrate the automatic change of color desired for every section and the colored background in the navigation bar.

A zoom to one of the frames to show the headline:

Remark:

The code needs two (or three) runs to stabilize.