Removing some lines in table

I'm afraid four different measures are neccessary:

1. Remove the vertical line with \multicolumn{1}{c|}{}.
2. Remove the horizontal line (segment) with \cline{2-4}.
3. Add a bit of space to the longest label on the top.
4. If you don't want the "inner" vertical lines for most of the table, I'd add them specifically for the head.

Result:

\begin{tabular}{|c|ccc|}
  \cline{2-4}
  \multicolumn{1}{c|}{}&
  \multicolumn{1}{c|}{\begin{sideways}ABCD\hspace*{1mm}\end{sideways}} &
  \multicolumn{1}{c|}{\begin{sideways}EFGH\end{sideways}} &
  \begin{sideways}IJKL\end{sideways} \\ \hline
  AA & 2 & 3 & 4 \\
  BB & 2 & 3 & 4 \\
  CC & 2 & 3 & 4 \\
  DD & 2 & 3 & 4 \\ \hline
\end{tabular}

You could use \multicolumn and \cline to get the desired output:

\documentclass{article}
\usepackage{rotating}
\begin{document}
\begin{table}[h]
\centering
\begin{tabular}{|c|ccc|}
\cline{2-4}
\multicolumn{1}{c}{}&
\multicolumn{1}{|c|}{\begin{sideways}ABCD\end{sideways}} &
\multicolumn{1}{c|}{\begin{sideways}EFGH\end{sideways}} &
\multicolumn{1}{c|}{\begin{sideways}IJKL\end{sideways}} \\ \hline
AA & 2 & 3 & 4 \\
BB & 2 & 3 & 4 \\
CC & 2 & 3 & 4 \\
DD & 2 & 3 & 4 \\ \hline
\end{tabular}
\caption{Tmp}
\label{tab:tmp}
\end{table}
\end{document}

In my opinion you can also omit the vertical lines in the header altogether, and also the border on top, left and right, giving

\begin{tabular}{c|ccc}
\multicolumn{1}{c}{}&
\multicolumn{1}{|c}{\begin{sideways}ABCD\end{sideways}} &
\multicolumn{1}{c}{\begin{sideways}EFGH\end{sideways}} &
\multicolumn{1}{c}{\begin{sideways}IJKL\end{sideways}} \\ \hline
AA & 2 & 3 & 4 \\
BB & 2 & 3 & 4 \\
CC & 2 & 3 & 4 \\
DD & 2 & 3 & 4 \\ \hline
\end{tabular}

This remove also the vertical lines among numbers:

\documentclass[spanish]{article}
\usepackage{babel}
\usepackage{rotating}
\begin{document}
\begin{tabular}{cccc|}
  \cline{2-4}
  \multicolumn{1}{c}{}&
  \multicolumn{1}{|c|}{
    \begin{sideways}ABCD\hspace*{1mm}\end{sideways}}&
  \multicolumn{1}{|c|}{
    \begin{sideways}EFGH\hspace*{1mm}\end{sideways}}&  
  \multicolumn{1}{|c|}{
    \begin{sideways}IJKL\hspace*{1mm}\end{sideways}}\\
  \hline
  \multicolumn{1}{|c|}{AA} & 2 & 3 & 4 \\
  \multicolumn{1}{|c|}{BB} & 2 & 3 & 4 \\
  \multicolumn{1}{|c|}{CC} & 2 & 3 & 4 \\
  \multicolumn{1}{|c|}{DD} & 2 & 3 & 4 \\ 
  \hline
\end{tabular}
\end{document}

Or with tabularx :

\documentclass{article}
\usepackage{rotating}
\usepackage{tabularx}
\begin{document}
\begin{tabularx}{3.5cm}{|X|XXX|}
  \cline{2-4}
  \multicolumn{1}{c|}{}&
  \begin{sideways}ABCD\hspace*{1mm}\end{sideways}&
  \begin{sideways}EFGH~\end{sideways}&
  \begin{sideways}IJKL\end{sideways} \\
\hline
AA\newline BB\newline CC\newline DD 
& 2\newline2\newline2\newline2 
& 3\newline3\newline3\newline4 
& 4\newline4\newline4\newline4\\  
\hline
\end{tabularx}
\end{document}

But maybe better with tabulary, and only booktabshorizontal lines:

\documentclass{article}
\usepackage{rotating}
\usepackage{tabulary,booktabs}
\begin{document}
\begin{tabulary}{3cm}{LCCCC}
\cmidrule[\heavyrulewidth]{2-4}&
\rotatebox{90}{ABCD}&
\rotatebox{90}{EFGH}&
\rotatebox{90}{IJKL} 
\\\midrule
AA\par BB\par CC\par DD &
 2\par 2\par 2\par 2 &
 3\par 3\par 3\par 4 &
 4\par 4\par 4\par 4
\\\bottomrule
\end{tabulary}
\end{document}