If you allow the factorization of $x^{2}+1$, then I don't think it is even necessary to find square roots of $-1$ mod prime powers. 

It's convenient to deal with the prime $2$ first, but this is easy, because the only condition imposed on $z$ to get the right power of $2$ dividing $z^{2}+1$ is that if $x$ is odd, we need $z$ odd.
  
If $p$ is an odd prime such that $p^{n}$ is the exact power of $p$ dividing $x^{2}+1$, then we just require that $p^{n}$ divides $z^{2} -x^{2}$, so we need $ z \equiv \pm x$ (mod $p^{n}$)  since $p$ is odd.

Notice then that, in all cases, there are $2^{k}$ possible congruences for $z$ (mod $x^{2}+1$), where $k$ is the number of distinct odd primes dividing $x^{2}+1$.