What if you use \lstinline for each cell, e.g. \lstinline!A!?
\usepackage{array} in your preamble.
then:
change this line: \begin{tabular}{|l|l|l|}
to this: \begin{tabular}{|m{width of cell}|m{width of cell} |m{width of cell}|}
the array package provides an extension to latex's tabular env. that will allow for the specification of the alignment of the text inside the cell. see the array package documentatio for more info.
It's a bit hacky, but you can use the escapechar keyword and just add extra lines so that they have the same length.
\begin{table}
\begin{tabular}{|l|l|}
\hline
Head1 & Head2 \\ \hline
\begin{lstlisting}[escapechar=\%]
A
B
%%
\end{lstlisting}
&
\begin{lstlisting}
A
B
C
D
\end{lstlisting}
\\ \hline
\end{tabular}
\end{table}
Edit: You only need to use the escape character for the last line (the above example has been modified to reflect this). Alternatively, if you don't mind an extra vertical padding and having to figure out the column widths by hand, you can solve this problem using the array package (as suggested by Mica) and replacing \begin{tabular}{|l|l|} with \begin{tabular}{|p{width}|p{width}|}. You might make width something like .5\linewidth.