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 if $x$ is even,  there are $2^{k}$ possible congruences for $z$ (mod $x^{2}+1$), where $k$ is the number of distinct primes dividing $x^{2}+1$. If $x$ is odd, then $z$ must be odd, and there are $2^{k}$ possible congruences for $z$ (mod $\frac{x^{2}+1}{2}$), where $k$ is the number of distinct odd prime divisors of $x^{2}+1$.

Notice that when $x^{2}+1$ is a prime power or twice a prime power, then we only get the "obvious" solutions, but the "extra" solutions you point out arise because $8^{2}+1$ and $12^{2}+1$ are not of such a form.