The answer is no. Assume FTSOC that there does exist $(a,b)$ that works. Since $a^2+b$ is a perfect square, it must be at least $(a+1)^2$, so $b\ge 2a+1$. Similarly, $a\ge 2b+1$, contradiction. $\blacksquare$