Adding color to a table column as a beamer overlay

Try conditionally defining a column type and using that:

\documentclass{beamer}
\usepackage{colortbl}
\begin{document}

\begin{frame}
\alt<2->{\newcolumntype{C}{>{\columncolor{red!30}}c}}{\newcolumntype{C}{c}}
\begin{tabular}[]{rC}
1 & 2 \\
3 & 4 \\
\end{tabular}
\end{frame}
\end{document}

Also, have a look at this link (german), very useful for rowcolor https://groups.google.com/forum/?fromgroups#!topic/de.comp.text.tex/v7qQFV3pjkw

Code from the linked discussion:

\documentclass{beamer}
\usepackage{colortbl}
\begin{document}
    \begin{frame}{Test}
        \begin{tabular}{l}
            \only<2>{\\\rowcolor{blue!50}}Test!
        \end{tabular}
    \end{frame}
\end{document}

You may define a custom column type associated with a custom color then change the definition of your color:

\documentclass{beamer}
\usepackage{colortbl}

\colorlet{mycol}{white}
\newcolumntype{A}{>{\columncolor{mycol}}c}

\begin{document}
\begin{frame}
\only<2>{\colorlet{mycol}{lime}}
\begin{tabular}[]{cA}
1 & 2 \\
3 & 4 \\
\end{tabular}
\end{frame}
\end{document}