Show plan before each section except the first one

Put the code you've mentioned after the \section to which you want it to apply from, rather than in the preamble

...
\section{Not in the list}
...
\AtBeginSection[]
  {
     \begin{frame}<beamer>
     \frametitle{Plan}
     \tableofcontents[currentsection]
     \end{frame}
  }
\section{First in the list}

I'm late to the party, but the solution by Joseph Wright does not help if you want to add that part to a beamer style.

A hack that I came up with:

\AtBeginSection[]
  {
    \ifnum \value{framenumber}>1
      \begin{frame}<beamer>
      \frametitle{Plan}
      \tableofcontents[currentsection]
      \end{frame}
    \else
    \fi
  }

This just checks if the framenumber is larger than 1 before printing the frame at the begin of each section. If the appearance of the first section is later than that, just switch the number to the appropriate one.