For the record, I have adapted Jake's code and began working on a new package called moderntimeline:
\usepackage{moderntimeline}
% Set the scale.
% I go up to 2013 otherwise some late dates overflow on the entry
\tlmaxdates{1999}{2013}
% Set the line width.
% This automatically sets the space under the top label to be 1pt more
\tlwidth{0.8ex}
% Set the labels text size
\tltext{\tiny}
And then a few examples:
\section{Experience}
\subsection{IT Experience}
\tlcventry[blue]{2006}{0}{Systems Engineer}{\href{http://www.orness.com}{ORNESS} then \href{http://www.alten.fr}{Alten}}{Sophia Antipolis}{}
{Consultant at France T\'el\'ecom
\begin{itemize}
\item Administration of Cfengine, FAI and the software package repository;
\item Renewal and industrialization of the software deployment system for Debian/Ubuntu;
\item Management of the Gforge (collaborative development web interface) platform;
\item Monitoring of the fleet of servers;
\item Writing of technical documentation.
\end{itemize}}

\tllabelcventry[purple]{1999}{2000}{1999--2000}{Paramedic}
{\href{http://www.croix-rouge.fr/}{French Red Cross}}{Paris Suburbs}{}
{Served in several volunteer missions as a paramedic}

\tldatelabelcventry[red]{2004}{July 2004}{Blue Collar Internship}
{\href{http://www.snecma.com}{SNECMA}}{Moissy-Cramayel}{}
{Assembled and equilibrated turbo reactors for planes}

\tldatecventry[green]{2005}{Student in Pedagogy (`Gestion Mentale')}
{\href{http://www.ifgm.org/}{IFGM}}{Bordeaux}{}
{Pedagogy, Didacticism, Cognitive Psychology}

Edit: Since moderncv aligns the left column to the right, there were weird things with dates, so I decided to put a white rectangle all over each entry to make sure the whole space was used. After that, my wife suggested I used a thin line to every entry to make things clearer, so now it looks like this (color and width of the thin line can be set):

Full examples can be seen in my updated CV.