A hacky solution is just to copy the contents of the colour theme .sty files (they aren't long) into a new tex file, cutting out the top and the bottom parts. So for example, for the whale theme just having a file containing:
\setbeamercolor*{palette primary}{use=structure,fg=white,bg=structure.fg}
\setbeamercolor*{palette secondary}{use=structure,fg=white,bg=structure.fg!75!black}
\setbeamercolor*{palette tertiary}{use=structure,fg=white,bg=structure.fg!50!black}
\setbeamercolor*{palette quaternary}{fg=white,bg=black}
\setbeamercolor*{sidebar}{use=structure,bg=structure.fg}
\setbeamercolor*{palette sidebar primary}{use=structure,fg=structure.fg!10}
\setbeamercolor*{palette sidebar secondary}{fg=white}
\setbeamercolor*{palette sidebar tertiary}{use=structure,fg=structure.fg!50}
\setbeamercolor*{palette sidebar quaternary}{fg=white}
\setbeamercolor*{titlelike}{parent=palette primary}
\setbeamercolor*{separation line}{}
\setbeamercolor*{fine separation line}{}
And then \input this just before you want the change to happen. Between frames.
One problem with this solution is that if you then change themes again, weird things will happen if theme 2 sets a colour, but theme 3 doesn't set it (because it leaves it as the default), you'll get the theme 2 colour showing through. So you'd need to add lines to your excised .sty files in order to reset it to default.
I'm sure there is a neater solution, however. It really should be easy to allow beamer to change colour themes (and other themes) on the fly. The only reason it can't is that the colour themes are in .sty files: the actual commands they define are, for the most part, valid in the body of the text...
Edit There is now a package on CTAN (which I maintain) that allows you to change the colour of a beamer presentation "on the fly". It doesn't, strictly speaking, change the colour theme, just the base colour of the structural elements. Here's an MWE:
\documentclass{beamer}
\usepackage{colourchange}
\useoutertheme{infolines}
\begin{document}
\selectmanualcolour{red}
\begin{frame}
This is a frame
\end{frame}
\selectmanualcolor{green}
\begin{frame}
This is a frame
\end{frame}
\end{document}