The function $RA(m,n)$ (as defined by the computation process described in the question description) satisfies the following conditions (where $A(m,n)$ is the standard Ackermann function):
$$
RA(m,n)=
\begin{cases}
1 & \text{for } m=0\\
1 + RA(m-1, 1) & \text{for } m>0 \text{ and } n=0\\
1 + RA(m, n-1) + RA(m-1, A(m, n-1)) & \text{for } m>0 \text{ and }n>0 \\
\end{cases}
$$
First two cases are trivial: $A(0, n)$ is given directly, without recurring any further, and $A(m,0)$ is defined as $A(m-1,1)$, so we just need to perform a single additional recursive call.
The third case is the slightly tricky one: in order to evaluate $A(m-1,A(m,n-1))$, we first need to compute the value of $A(m,n-1)$, which takes $RA(m,n-1)$ steps. After that, we are computing $A(m-1,\cdot)$, where $\cdot$ is the just-computed value of $A(m,n-1)$ (i.e. it doesn't bring in any further recursive calls), which is represented by the last term.
It is now not too difficult to see that $RA(m,n)\geq A(m,n)$ for $m\geq 1$ ($m=0$ is a special case, since it involves no additional recursion).
We can also use the third line repeatedly until we reach $n=0$ and finish by applying the second one to obtain the following equality which expresses $RA(m,n)$ using just $RA(m-1,\cdot)$:
$$RA(m,n)=(n+1) + RA(m-1,1) + \sum_{k=0}^{n-1} RA(m-1,A(m,k))$$
Since $A(3,n)=2^{n+3}-3$ and we already know $RA(2,n)=2n^2+7n+5$, we can
evaluate $RA(3,n)$ exactly as:
$$RA(3,n) = 128\frac{4^n-1}{3} - 40\left(2^n-1\right) + 3n + 15$$
(the strange-looking terms are results of summing geometric progressions)
This subsequently allows us to reach a little bit further in the computations and find that $RA(4,1)=2862984010$ but beyond this point the numbers grow very fast. Furthermore, unlike the nice polynomials (for $m\leq 2$) and exponentials (for $m=3$), exponential towers and further hyperoperations which are lurking in $A(m,n)$ for $m>3$ do not play well with simple summation, so I doubt there would be any simple exact expression for $RA(m,n)$ with $m>3$.
Of course, this doesn't stop this function from having some explicit (and possibly even tight) bounds in terms of $A(m,n)$ or some similar function; I even have an idea of how such bounds might looks like; I will try to play with and update the answer if it yields anything interesting.
The induction is on $n$.
Your first step is correct; for $n=0$ we have that:
$A(1,0)=A(0,1)=1+1=2$,
that is $n+2$ for $n=0$.
For the induction step, we have to assume that the property holds for $k$ and prove it for $k+1$.
Thus, we assume the induction hypotheses: $A(1,k)=k+2$, and we have to compute:
$A(1,k+1)=A(0,k+2)=k+3$,
which is $n+2$ for $n=k+1$.
Best Answer
Notice that the Ackermann function is discrete. This means we may use $a>b\iff a\ge b+1$, which may be used on the step you found troublesome:
$$A(m+1,n+1)=A(m,A(m+1,n))\ge A(m+1,n)+1\ge(n+1)+1>n+1\tag{$\star$}$$
and the whole proof would be as follows:
Base case $m=0$: For all $n$, $A(0,n)=n+1\ge n$ follows.
Induction hypothesis $m\implies m+1$: Assume for some $m$ that for all $n$, $A(m,n)\ge n$. Then:
Base case $n=0$: $A(m+1,0)=A(m,1)>1>0$ follows.
Induction hypothesis $n\implies n+1$: See $(\star)$.
Therefore $A(m+1,n)>n$ for all $n$.
Therefore ($A(m,n)>n$ for all $n$) for all $m$.
Notice the indented steps all use a fixed $m$ i.e. the same value of $m$. If you write (for all $m$) on those lines, then you are not proving ($A(m+1,n)>n$ for all $n$), which has a fixed value of $m$.