You can, indeed, define that recursively as you've begun. You've certainly got the general idea down, starting with $n_0$ as you've done. To pass to recursion, if we've got $n_0,...,n_k$, then let $n_{k+1}$ be the greatest integer $n$ such that $n\leq 10^{k+1}\left(x-\sum_{j=0}^kn_j10^{-j}\right).$ This is enough to prove existence. Of course, we don't have uniqueness ($1=0.9999...$), but this is a well-defined recursive algorithm to give you what you want.
Edit: I missed a rather large issue, here. Note that $n_0$ as defined above need not be a decimal digit, and can in fact be any nonnegative integer! All the others will end up being decimal digits, as it turns out, so this recursion takes care of all the decimal places to the right of the decimal point, but not those to the left.
As a fix, do it this way, instead. Note that the set $\{10^m:m\in\Bbb Z\}$ is unbounded. Thus, by similar reasoning to what you used, there is some greatest $m\in\Bbb Z$ such that $10^m\leq x$. Then $x<10^{m+1}$, so $10^{-m}x<10$, and let $n_m$ be the greatest integer $n$ such that $n\leq 10^{-m}x$--so of necessity, we will have $0\leq n_m\leq 9$, since $0<10^{-m}x<10$.
Now, for the recursion, suppose we've just defined $n_k$. Take $n_{k-1}$ to be the greatest integer $n$ such that $10^{k-1}n\leq x-\sum_{j=k}^mn_j10^j.$
You'll need to show that for all $k\leq m$, we have $0\leq n_k\leq 9$ (a fairly simple induction from $m$ toward $-\infty$, with the $k=m$ case holding as noted above), and that $x=\sum_{j=-\infty}^mn_j10^j.$ Note that we are now matching $n_j$ with $10^j$, rather than $10^{-j}$. You can alter this if you like, though the notation will become a bit more complicated.