Use column-separator & (ampersand) inside \newenvironment

The problem is that the \begin{...} and \end{...} pair commands automatically create a "group" so that, in effect, the & and \\ are "out of scope" for the tabular, while inside the "production" environment they just show up at a place where the compiler is not expecting them.

A second problem with your definitions is that, even if they would work, they would be adding an extra \\ at the end of the tabular, adding an unwanted space at the end. Perhaps some more appropriate definitions would be

\documentclass[a4paper,10pt]{article}

\newcommand{\production}[1]{#1 ::= &}
\newenvironment{grammar}{\tabular{p{3cm}l}}{\endtabular}

\begin{document}
\begin{grammar}
\production{XmlStartTag} ... \\
\production{XmlOtherTag} ... \\
\production{XmlEndTag} ...
\end{grammar}
\end{document}

Note no \\ at the end of the last production. Also in the definition of the grammar you don't need to repeat the work of \begin/\end, and you can instead directly use \tabular and \endtabular.

EDIT: The answer was completely wrong; sorry to those who had upvoted.

I found a trick when trying to solve this question. You can use the environ package and define the production environment as follows:

\usepackage{environ}
\NewEnviron{production}[1]{%
  \toks0={\noindent\ignorespaces#1 ::= &}%
  \toks2=\expandafter{\BODY}%
  \toks4={\\}%
  \xdef\gtemp{\the\toks0 \the\toks2 \the\toks4 }%
  \aftergroup\gtemp
}

\BODY is the content of the environment. The code works as follows: store \noindent\ignorespaces#1 ::= & into the token register \toks0, then store \BODY (expanded by \expandafter) into \toks2, and the trailing code \\ into \toks4. Put everything together into the global token list \gtemp. The \xdef expands \the\toks0, \the\toks2, and \the\toks4 (spaces after the numbers are important). Finally, \aftergroup\gtemp places the \gtemp after the end of the group formed by \begin{production}...\end{production}, so that this group does not interfere with groups produced by the tabular. See the answer to the question I mention above.

Two questions for more experienced TeXers: can I use \unexpanded to do this better? Is there a good way of executing a lot of stuff \aftergroup: I hate having to define \gtemp globally.

It has nothing to do with macro expansion but with grouping: Cells in a tabular build a group. You are starting an environment in one group and close it in the next. Use better a command \production.