As noted by David Speyer following Robert Israel's answer, given the factorization of $x^{2}+1$, then it is not 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$.
To be more explicit, if $x$ is even, let the prime factorization of $x^{2}+1$ be $x^{2}+1 = \prod_{i=1}^{k}p_{i}^{n_{i}}$, where the $p_{i}$ are distinct primes, and if $x$ is odd, let the prime factorization of $\frac{x^{2}+1}{2}$ be $\frac{x^{2}+1}{2} = \prod_{i=1}^{k}p_{i}^{n_{i}}$.
For any ordered $k$-tuple of signs $(\epsilon_{1}, \ldots, \epsilon_{k})$, solve (simultaneously) $z \equiv \epsilon_{i} x$ (mod $p_{i}^{n_{i}}$) for each $i$. If $x$ is odd, also impose the condition that $z$ is odd.
In either case, this gives $2^{k}$ distinct possibilities for the congruence of $z$ (mod $x^{2}+1$) which yield $x^{2} + 1 | z^{2}+1$, and there are no other valid congruences (where, as noted earlier, $k$ is the number of distinct odd prime divisors of $x^{2}+1$).