Underbrace under table, stretching over multiple columns

Yes, you need to pad the contents that is spanned with the appropriate spaces:

\documentclass{article}
\begin{document}
\begin{tabular}{r|c|c|c|c}
  $i$ & 0 & 1 & 2 & 3 \\
  \multicolumn{1}{c}{} & 
    \multicolumn{3}{@{}c@{}}{$\underbrace{\hspace*{\dimexpr6\tabcolsep+2\arrayrulewidth}\hphantom{012}}_{a_1}$} & 
    \multicolumn{1}{@{}c@{}}{$\underbrace{\hspace*{2\tabcolsep}\hphantom{3}}_{a_2}$}
\end{tabular}

\bigskip

\begin{tabular}{r|c|c|c|c}
  $i$ & 0 & 1 & 2 & 3 \\[\dimexpr-\normalbaselineskip+1ex]
  \multicolumn{1}{c}{} & 
    \multicolumn{3}{@{}c@{}}{$\underbrace{\hspace*{\dimexpr6\tabcolsep+2\arrayrulewidth}\hphantom{012}}_{a_1}$} & 
    \multicolumn{1}{@{}c@{}}{$\underbrace{\hspace*{2\tabcolsep}\hphantom{3}}_{a_2}$}
\end{tabular}
\end{document}​

Using the column specification @{}c@{} removes any column padding for that (multi-)cell entry. The \underbrace is placed under a space of size 6\tabcolsep+2\arrayrulewidth and text of horizontal width equivalent to 012 (in the first \underbrace), which is the same amount of structured information in the tabular.

I've added a second alternative that adjusts the vertical alignment under the tabular, which I think is better.

If you're not sold on a tabular, the easier thing to do is of course:

\documentclass{article}
\usepackage{mathtools}% http://ctan.org/pkg/mathtools
\newcommand{\sep}{\mathclap{|}}% Separator
\begin{document}
\[
  i \quad\sep\underbrace{\quad 0 \quad\sep\quad 1 \quad\sep\quad 2 \quad}_{a_1}
  \sep
  \underbrace{\quad 3\vphantom{|} \quad}_{a_2}\sep
\]
\end{document}​

mathtools provides \mathclap - a zero-width box in math mode that centres its contents.

\documentclass{article}

\begin{document}

\begin{tabular}{r|c|c|c|c}
  i & 0 & 1 & 2 & 3 \\
  \multicolumn{1}{c}{} & \multicolumn{3}{c}{\upbracefill}& \multicolumn{1}{c}{\upbracefill}\\[-1ex]
  \multicolumn{1}{c}{} & \multicolumn{3}{c}{$\scriptstyle a_1$}& \multicolumn{1}{c}{$\scriptstyle a_2$}\\
\end{tabular}


\end{document}