Verwende für die Nodes mit der Beschriftung die gleiche Höhe und Tiefe wie für die Nodes in der Matrix. Also
    \tikzset{ZeilenNummer/.style={font=\tiny,text \tikzset{ZeilenNummer/.style={
    	font=\tiny,
        text height=\ht\strutbox,text depth=\dp\strutbox}}
depth=\dp\strutbox,
        text width=1em,align=center
    }}
![alt text][1]
  [1]: http://texwelt.de/wissen/upfiles/tw_zeilenbeschriftung.png
![alt text][1]
Code:
    \documentclass[varwidth, margin=5mm]{standalone}
    \usepackage[ngerman]{babel}
    \usepackage{amsmath, amssymb, relsize, tikz}
    \usetikzlibrary{matrix, fit, positioning}
    \begin{document}
    \begin{tikzpicture}[
    font=\footnotesize, 
    ]
    % Matrix
    \matrix (m) [
    matrix of math nodes,
    inner sep=0pt, 
    column sep=0.5em, row sep=0pt,
    nodes={
    text height=\ht\strutbox, text depth=\dp\strutbox,
    inner sep=0.0em,text width=1em,align=center},
    ]
    {%
    a_1 \\ a_2 \\ a_3 \\ \vdots \\ a_4 \\
    };%
    % Zeilennummerierung
    \tikzset{ZeilenNummer/.style={font=\tiny,text \tikzset{ZeilenNummer/.style={
	font=\tiny,
        text height=\ht\strutbox,text depth=\dp\strutbox}}
depth=\dp\strutbox,
        text width=1em,align=center
    }}
    \node[ZeilenNummer, left = 0.5em of m-1-1]{$(1)$};
    \node[ZeilenNummer, left = 0.5em of m-2-1]{$(2)$};
    \node[ZeilenNummer, left = 0.5em of m-3-1]{$(3)$};
    \node[ZeilenNummer, left = 0.5em of m-4-1, red]{$\vdots$};
    \node[ZeilenNummer, left = 0.5em of m-5-1]{$(3)$};
    \end{tikzpicture}
    \end{document}
  [1]: http://texwelt.de/wissen/upfiles/tw_zeilenbeschriftung_1.png