Your best bet here, in my opinion, is to duplicate the structure of your table on the frames that you need using a regular tabular environment.
In terms of headers, also duplicate the header but use \widthof{...} (from the calc package) to get the spacing right across frames. The argument of \widthof{...} should be the widest element within the column across all frames:
\documentclass{beamer}
\usepackage{lmodern}% http://ctan.org/pkg/lmodern
\usepackage{calc}% http://ctan.org/pkg/calc
\begin{document}
\begin{frame}{My frame title}
\begin{tabular}{cc}
This is a very long header & Here is another header \\ \hline
fooooooooooo & Bar\\
fooooooooooo & Bar\\
fooooooooooo & Bar\\
fooooooooooo & Bar\\
fooooooooooo & Bar\\
fooooooooooo & Bar\\
\end{tabular}
\end{frame}
\begin{frame}{My frame title}
\begin{tabular}{cc}
\makebox[\widthof{This is a very long header}][c]{Different header} &
\makebox[\widthof{Here is another header}][c]{Short header} \\ \hline
fooooooooooo & Bar\\
fooooooooooo & Bar\\
fooooooooooo & Bar\\
fooooooooooo & Bar\\
fooooooooooo & Bar\\
fooooooooooo & Bar\\
\end{tabular}
\end{frame}
\end{document}

\widthof{...} will ensure that the horizontal spacing is preserved without respecifying it (in the literal/length sense, as in 50pt, say).