Show $a^2 + b^2 + 1 \equiv 0 \mod p$ always has a solution if $p = 4k+3$

I'm not sure how to modify/fix your construction, but for reference the "standard" argument is that since $p$ is prime, $-a^2$ and $b^2+1$ both run over $(p+1)/2$ distinct values for $a,b\in \mathbb{F}_p$, and so must agree on at least one value.

Notice that this works for any (odd) prime, not just those of the form $4k+3$, but that in the case $p\equiv 1 \bmod 4$ you can additionally take $a=0$.

The argument given by user7530 is what I would recommend as well. It gets everything done inside $\Bbb{F}_p$.

Your intuitive leap can also be justified. The mapping $z\mapsto z\overline{z}$ is known as the relative norm map. We can view it differently. The Galois theory of extensions of finite fields tells us that the non-trivial $\Bbb{F}_p$-automorphism of $\Bbb{F}_{p^2}$ is the Frobenius mapping $z\mapsto z^p$. So we know $N(z)=z\overline{z}=z^{p+1}$ for all $z\in\Bbb{F}_{p^2}$.

The key to success is to recall the fact that the multiplicative groups $\Bbb{F}_{p^2}^*$ and $\Bbb{F}_{p}^*$ are cyclic of respective orders $p^2-1$ and $p-1$. The basic facts about cyclic groups tell us that raising to power $p+1$ is a surjective homomorphism between the two groups. Therefore any element of $\Bbb{F}_p$ is the norm of some element of $\Bbb{F}_p$ - the element $-1$ in particular.

The assumption $p\equiv3\pmod4$ is used as it gives us the description $\Bbb{F}_{p^2}=\Bbb{F}_p[i]$, where $i^2=-1$. User7530's argument is immune to that detail.