The only solution I see is to decrease the font size to \tiny combined with a rotation of the whole table. For the latter one you can use the sidewaystable environment from the rotating package instead of the tabular environment.
Code: Select all
\begin{sidewaystable}
% table contents (with caption)
\end{sidewaystable}