Wenn man hinter die `\addplot` jeweils einen `label` Befehl setzt, dann kann man mit `\ref` auch außerhalb der einzelnen `axis` Umgebungen auf die Legendenbildchen zu greifen und damit in einer Matrix eine gemeinsame Legende erstellen. Dazu lade ich zusätzlich die TikZ Bibliothek `matrix`. 
    \documentclass[margin=5pt]{standalone}
    \usepackage{pgfplots}
    \pgfplotsset{compat=newest}
    \usetikzlibrary{matrix}
    \begin{document}
    \begin{tikzpicture}[node font=\footnotesize,
      farbe/.style={draw=#1!80!black,fill=#1!20}] 
    \pgfplotsset{
        height=4cm, width=7cm,
        scale only axis, 
        xmin=0.5, xmax=4.5,
    }
    % Barplots
    \begin{axis}[
        axis x line=bottom, 
        xtick={0.5, 1, 2, 3, 4, 4.5},
        xticklabels={,2009, 2010, 2011, 2012, }, 
        axis y line=left, ylabel=Label 1,
        ymin=4, ymax=14,
        ytick={4,6,...,14}, 
        ymajorgrids=true, 
        ybar=4pt, 
        bar width=8pt
      ] 
      \addplot[farbe=red] plot coordinates 
        {(1, 6) (2, 8) (3, 5) (4, 13)};
        \label{pgfplots:plot1}
      \addplot[farbe=blue] plot coordinates 
        {(1, 5) (2, 6) (3, 12) (4, 5)};
        \label{pgfplots:plot2}
    \end{axis}
    % Linie
    \begin{axis}[
        axis x line=none, xtick=\empty,
        axis y line=right, ylabel=Label 2, 
        ymin=39, ymax=44, 
        ytick={39,...,44}, 
      ] 
      \addplot[red!50!blue,mark=*] plot coordinates 
        {(01, 40.4) (02, 41.6) (03, 42) (04, 42.3)};
        \label{pgfplots:plot3}
    \end{axis}
    % Legende
    \matrix[
        matrix of nodes,
        anchor=north west,
        draw,% Rahmen um Legende
        inner sep=0.2em,
        column 1/.style={nodes={anchor=center}},
        column 2/.style={nodes={anchor=west}},
2/.style={nodes={anchor=west},font=\strut},
        draw
      ]
      at([xshift=1.5cm]current axis.north east){
        \ref{pgfplots:plot1}& erster Barplot\\
        \ref{pgfplots:plot2}& zweiter Barplot\\
        \ref{pgfplots:plot3}& Linie\\};
    \end{tikzpicture} 
    \end{document}
Ergebnis nach zwei Durchläufen (wegen der Referenzen):
![alt text][1]
  [1]: http://texwelt.de/wissen/upfiles/legende2_2.pnghttp://texwelt.de/wissen/upfiles/legende2_3.png