How to prove that this function is primitive recursive?

I think the only different in what you want to prove and the usual primitive recursion is the coordinate that you are iterating. Therefore the following may be helpful Prove the function $\Theta$ defined by $\Theta(x,y) = (y,x)$ is primitive recursive. More specifically, the usual basic primitive recursive functions include a projection function $\pi_i(x_1, ..., x_n) = x_i$ and it has composition scheme. If $f$ is primitive recursive and $g_1, ..., g_n$ are primitive recursive, then $f(g_1, ..., g_n)$ is primitive recursive. Let $I$ be the identity function on two argument. Therefore define $\Theta(x,y) = I(\pi_2(x,y), \pi_1(x,y))$. Then I think you can prove your primitive recursion scheme from the usual one.

I came across this question because I wanted to prove something very similar myself (while teaching a course on computability, so this is not homework for me!). Unfortunately the question was posed in such a way that almost nobody seems to have understood the real issue, and in particular I found no appropriate reply here or at MathOverflow. So I'll try to give my best shot at it, but I would much like to learn a simpler answer (given that it was homework, maybe the OP learned a solution by now?). So firstly, the difficulty is that while the basic primitive recursion schema allows passing on additional parameters that are not object of the recursion ($\bar x$ in the text of the question) unchanged, the question asks what to do when this parameter is modified by the application of $\pi$. That this is is not in general innocent can be shown by the Ackermann function, which operates by a similar modification of its non-recursion parameter, and which is not primitive recursive (of course the modification is here in terms of the Ackermann function itself while in the question $\pi$ must be primitive recursive, so we may still hope for a positive answer). I'll first assume that $\pi$ satisfies $\pi(x,y)\leq y$ for all $x,y$, so that the recursion relations only decreases the additional parameter $y$. In that case one has the following solution, somewhat similar to how http://en.wikipedia.org/wiki/Course-of-values_recursion is handled: define first another function $H$ of two arguments by $H(x,y)=\left<h(x,0),\ldots,h(x,y)\right>$, the encoding of the indicated list into a single number; although apparently $H$ is more complicated than $h$, can be defined more directly by primitive recursion. Indeed what is needed is a primitive recursive function $G$ to compute $H(x+1,y)=\left<h(x+1,0),\ldots,h(x+1,y)\right>$ given the values $x$, $y$, and $H(x,y)=\left<h(x,0),\ldots,h(x,y)\right>$. It should return a list with final component $h(x+1,y)=g(x,y,h(x,\pi(x,y)))$ where $h(x,\pi(x,y))$ is one of the components of $H(x,y)$ by the assumption $\pi(x,y)\leq y$. This component can be computed from $x,y,H(x,y)$ by a primitive recursive function, say $G_0(x,y,z)$ with $z$ taken to be $H(x,y)$. Since the only thing $G_0$ needs to do with the list $z$ is select a component from it, we may assume that it returns the same value whenever $z$ is replaced by a longer list containing $z$ as prefix. Now we can define $G$ primitive recursively by $$ \begin{align*} G(x,0,z) &= \left< G_0(x,0,z) \right> \\ G(x,y+1,z) &= \mathit{append}(G(x,y,z),G_0(x,y+1,z)) \end{align*} $$ where $\mathit{append}$ adds an element to the list encoded as its first argument. (Note how we avoided having to modify $z$ in the recurrence for $G$, as this would have got us into a chicken-and-egg situation.) We can now define $H(x,y)$ by primitive recursion on $x$ using $G$ (I leave computing $H(0,y)$ as an exercise), and finally $h(x,y)$ by taking the final element of the list encoded by $H(x,y)$. (Another more brute-force approach to this case is to define $h'(z)$ by $h'(\langle x,y\rangle)=h(x,y)$ for an encoding $\langle x,y\rangle$ of the pair $(x,y)$, which encoding may be taken to be bijective (every $z$ encodes a pair) and monotonic (increasing $x$ or $y$ always increases the code $\langle x,y\rangle$; this is true for any reasonable encoding). Then since $\langle x+1,y\rangle > \langle x, \pi(x,y)\rangle$, the recurrence relation that $h$ must satisfy leads to a course-of-values recursion for $h'$, which we know how to handle.) Now most primitive recursive functions $\pi$ of two arguments do of course not satisfy $\pi(x,y)\leq y$ for all $x,y$, and if not the above methods do not work. However, increase in the non-recursive argument does not form a real obstruction to the computation of $h$, since for each pair $(x+1,y)$ we can predict (using $\pi$) how many values $(x,y')$ we need to compute $f$ for first, and so on for decreasing $x$. So intuitively we can compute $h(x,y)$ by computing successive "rows" (i.e., with fixed $x$) up to a point computable in advance. (This is unlike for the Ackermann function, where each row needs to be developed only to a finite extent, but not predictable until you already know the Ackermann function itself.) To handle the general case, I first reduce to the case that actually $\pi(x,y)\geq y$ for all $x,y$ and also that $\pi(x,y)$ is monotonic in $y$, while at the same time generalising to the case that $g$ depends (apart from on $x$ and $y$) not only on the value $h(x,\pi(x,y))$, but on the entire (encoded) row $\left<h(x,0),\ldots,h(x,\pi(x,y))\right>$; as we have seen this generalisation does not complicate matters essentially. To obtain the reduction, replace $\pi$ by $\pi'$ defined as $\pi'(x,y)=\mathrm{max}(y,\pi(x,0),\ldots,\pi(x,y))$ if necessary. Now the feature that allows predicting how much values need to be pre-computed, is that for given $x,y$ the final value $l(x,y)$ of the sequence $y$, $\pi(x-1,y)$, $\pi(x-2,\pi(x-1,y))$, ... $\pi(0,\pi(1,\ldots\pi(x-1,y)\ldots))=l(x,y)$ of maximal $y$-values needed respectively for $x$, $x-1$, $x-2$, ..., $0$ can be computed primitive-recursively. Indeed this value is given by $l(x,y)=L(x,x,y)$ where $L$ satisfies $$ \begin{align*} L(0,x,y) &= y, \\ L(i+1,x,y) &= \pi(x-i,L(i,x,y)). \end{align*} $$ Note that by our assumption on $\pi$, the function $l$ is also monotonic in $y$ and satisfies $l(x,y)\geq y$ for all $x,y$. Moreover $l(x+1,y)=l(x,\pi(x,y))$ by definition of $l$. Now my idea is to define a different function $H(x,z)$ to help define $h$, and which encodes the list of values $h(x,y)$ for all $y$ with $l(x,y)\leq z$. The function $h$ can then be defined by taking $h(x,y)$ to be the value in the list $H(x,l(x,y))$ at index $y$, which is guaranteed to exist (and propbably the last value on the list). The point of $H$ is that, by what we know about $l$, the list encoded by $H(x,z)$ is finite, and $H(x,z)$ contains all previous values $h(x,y)$ that one needs to know to compute the (in general much fewer) values encoded in the list $H(x+1,z)$. So it should be possible to define $H$ by primitive recursion on $x$, with $z$ as an unchanging second argument. I'm a bit tried of giving details though (and I'm sure the reader is as well) so I'll stop here.