Obtaining binomial coefficients without "counting subsets" argument
A simple-minded approach is to solve the two variable recurrence relation iteratively, that is, knowing $a_{n,0}$ find $a_{n,1}$, then $a_{n,2}$, etc.
We must have
$$\begin{eqnarray*}
a_{n,1} &=& a_{n-1,1}+a_{n-1,0} \\
&=& a_{n-1,1}+1,
\qquad a_{1,1}=1.
\end{eqnarray*}$$
This is a one variable recurrence relation of the form
$$b_n = b_{n-1}+1, \qquad b_1 = 1.$$
This can be solved by the usual methods.
We find
$a_{n,1} = n.$
Next we have $$\begin{eqnarray*} a_{n,2} &=& a_{n-1,2}+a_{n-1,1} \\ &=& a_{n-1,2}+n-1, \qquad a_{2,2}=1. \end{eqnarray*}$$ This is another simple recurrence relation. We find $a_{n,2} = n(n-1)/2.$
At the next step, $$\begin{eqnarray*} a_{n,3} &=& a_{n-1,3}+a_{n-1,2} \\ &=& a_{n-1,3} + \frac{1}{2}(n-1)(n-2), \qquad a_{3,3}=1. \end{eqnarray*}$$ This implies $a_{n,3} = n(n-1)(n-2)/6.$
This process can be repeated to build up $a_{n,k}$ for any $k$. At some point a pattern will be noticed and the principle of induction can be applied.
If you define $a_{n,k}=\binom nk$ to be the coefficient of $X^k$ in $(1+X)^n$ (with no combinatorial meaning attached), then you easily find $\binom nk=\binom {n-1}{k-1}+\binom{n-1}k$ for all $n,k\geq1$ (as you indicated in the question). Also $\binom n0=1$ for all $n\geq0$, and $\binom0k=0$ for all $k>0$. Expanding the second term of the recurrence relation recursively, with $\binom0k=0$ as terminating clause, gives $$ \binom n k=\sum_{0\leq i<n}\binom i{k-1} \qquad\text{for $k\geq1$ and all $n\geq0$.} $$ Now from the fact that $n\mapsto\binom n0$ is a polynomial function (of $n\in\mathbf N$) of degree$~0$ (namely the constant function$~1$) it follows easily by induction that $n\mapsto\binom nk$ is a polynomial function of degree$~k$ (summing a polynomial function of$~n$ increases the degree by$~1$). Moreover the first $k$ values $\binom ik$ for $0\leq i<k$ of the polynomial function are all$~0$, so the polynomial has roots $0,1,2,\ldots,k-1$. It therefore necessarily takes the form $\binom nk=c_k(n-0)(n-1)\ldots(n-(k-1))$ for some constant $c_k$. Using the recursion (at some point one does need to compute something) the first nonzero term $\binom kk$ of the sequence $n\mapsto\binom nk$ can be shown to be$~1$ for every$~k$, and it follows that $c_k=1/(k(k-1)(k-2)\ldots(k-(k-1))=\frac1{k!}$. Then $$ \binom nk = \frac{n(n-1)\ldots(n-(k-1))}{k!}, $$ which you may, if you feel so inclined, write as $\binom nk = \frac{n!}{k!(n-k)!}$ as long as $k\leq n$.
Look mom, no counting!