Without loss of generality, assume that $|b| \leq |a|$. If $b=0$, then $a$ must be a perfect square. So $(a = k^{2}, b = 0)$ for each $k \in \mathbb{Z}$ is a solution.

Now we consider the case $b \neq 0$. Because $a^{2}+4b$ is a perfect square, the quadratic equation

$$x^{2} + a x - b = 0 \tag{*}$$

has two non-zero integral roots $x_{1}, x_{2}$.

Then $x_{1} + x_{2} = -a$ and $x_{1} x_{2} = -b$, and from this it follows that
$$\frac{1}{|x_{1}|} + \frac{1}{|x_{2}|} \geq \left| \frac{1}{x_{1}} + \frac{1}{x_{2}} \right| = \frac{|a|}{|b|} \geq 1$$

Hence there is at least one root, say $x_{1}$, such that $|x_{1}| \leq 2$.

There are the following possibilities.

(1) $x_{1} = 2$. Substituting $x_{1} = 2$ into (*) we get $b = 2a + 4$. So we have $b^{2} + 4a = (2a + 4)^{2} + 4a = 4a^{2} + 20a + 16 = (2a + 5)^{2} - 9$. It is easy to see that the solution in non-negative integers of the equation $x^{2} - 9 = y^{2}$ is $(3, 0)$. Hence $2a + 5 = \pm 3$. From this we obtain $a = -4, b = -4$ and $a = -1, b = 2$. The latter should be rejected because of the assumption $|a| \geq |b|$.

(2) $x_{1} = -2$. Substituting $x_{1} = -2$ into (*) we get $b = 4 - 2a$. Hence $b^{2} + 4a = 4a^{2} - 12a + 16 = (2a - 3)^{2} + 7$. It is easy to show that the solution in non-negative integers of the equation $x^{2} + 7 = y^{2}$ is $(3, 4)$. Hence $2a - 3 = \pm 3$. From this we obtain $a = 3, b = -2$.

(3) $x_{1} = 1$. Substituting $x_{1} = 1$ into (*) we get $b = a + 1$. Hence $b^{2} + 4a = a^{2} + 6a + 1 = (a + 3)^{2} - 8$. It is easy to show that the solution in non-negative integers of the equation $x^{2} - 8 = y^{2}$ is $(3, 1)$. Hence $a + 3 = \pm 3$. From this we obtain $a = -6, b = -5$.

(4) $x_{1} = -1$. Substituting $x_{1} = -1$ into $(*)$ we get $b = 1 - a$. Then $a^{2} + 4b = (a - 2)^{2}$, $b^{2} + 4a = (a + 1)^{2}$. Consequently, $a = k, b = 1 - k$ ($k \in \mathbb{Z}$) is a solution.

Testing these solutions and by symmetry we obtain the following solutions
$$(-4, -4),\ (-5, -6),\ (-6, -5),\ (0, k^{2}),\ (k^{2}, 0),\ (k, 1 - k)$$
where $k$ is an arbitrary integer. (Observe that the solution $(3, -2)$ obtained in the second possibility is included in the last solution as a special case.)

Without loss of generality assume that $|b| \leq |a|$. Then $a^{2} + 4b \leq a^{2} + 4|a| < a^{2} + 4|a| + 4 = (|a| + 2)^{2}$. Given that $a^{2} + 4b$ is a perfect square and since $a^{2} + 4b$ and $a^{2}$ have the same parity then $a^{2} + 4b \neq (|a| + 1)^{2}$, so
$$a^{2} + 4b \leq a^{2} \tag{1}$$

Case 1. $a^{2} + 4b = a^{2}$. Then $b = 0$ and $a$ must be a perfect square. So $a = k^{2}, b = 0$ ($k \in \mathbb{Z}$) is a solution.

Case 2. $a^{2} + 4b = (|a| - 2)^{2}$. Then $b = 1 - |a|$, therefore $b^{2} + 4a = a^{2} - 2|a| + 4a + 1$ must be a perfect square.

If $a > 0$ then $b^{2} + 4a = (a + 1)^{2}$ is a perfect square for each $a \in \mathbb{Z}$. Consequently $a = k$ and $b = 1 - k$ ($k \in \mathbb{Z}^{+}$) is a solution.

If $a < 0$ then $b^{2} + 4a = m^{2} - 6m + 1$ must be a perfect square, where $m = -a > 0$. For $m \geq 8$
$$(m - 3)^{2} > m^{2} - 6m + 1 > (m - 4)^{2}$$
therefore $m < 8$. If $m = 1, 2, 3, 4, 5$ then $m^{2} - 6m + 1 < 0$. If $m = 6$, $m^{2} - 6m + 1 = 1$ is a perfect square thus $a = -6$ and $b = -5$ is a solution. If $m = 7$, $m^{2} - 6m + 1 = 8$ is not a perfect square.

Case 3. $a^{2} + 4b \leq (|a| - 4)^{2}$. Since $|b| \leq |a|$ then $b \geq -|a|$, thus $a^{2} - 4|a| \leq a^{2} + 4b \leq (|a| - 4)^{2}$. It follows that $|a| \leq 4$. We have following possibilities:

(a) $|a| = 4$. Then $16 + 4b = 0$ or $b = -4$. Thus $b^{2} + 4a = 16 \pm 16$ must be a perfect square. So $a = -4$ and $b = -4$.

(b) $|a| = 3$. In this case $a^{2} + 4b = 9 + 4b \leq 1$, then $9 + 4b = 0$ or $9 + 4b = 1$. The equation $9 + 4b = 0$ does not have integer solutions. The solution of the second equation is $b = -2$. Then $b^{2} + 4a = 4 \pm 12$ must be a perfect square, thus $a = 3$.

(c) $|a| = 2$. $a^{2} + 4b = 4 + 4b \leq 4$. Since $4 + 4b$ is even and must be a perfect square then $4 + 4b = 4$ or $4 + 4b = 0$. Therefore $b = 0$ or $b = -1$. If $b = 0$, $b^{2} + 4a = \pm 8$ is not a perfect square. If $b = -1$ then $b^{2} + 4a = 1 \pm 8$ is a perfect square if $a = 2$. Thus $a = 2$ and $b = -1$ is a solution.

(d) $|a| = 1$. Then $a^{2} + 4b = 4b + 1 \leq 9$. Since $4b + 1$ must be an odd perfect square then $4b + 1 = 1$ or $4b + 1 = 9$. So $b = 0$ or $b = 2$. If $b = 0$, $b^{2} + 4a = \pm 4$, then $a = 1$. If $b = 2$ then $a = -1$, but this is not possible because $|b| \leq |a|$. Thus $a = 1$ and $b = 0$ is a solution in this case.

(e) $|a| = 0$. Since $|b| \leq |a|$ then $b = 0$.

Testing these solutions and by symmetry we obtain the following solutions:
$$(k^{2}, 0),\ (0, k^{2}),\ (k, 1 - k),\ (-6, -5),\ (-5, -6),\ (-4, -4)$$
where $k$ is an arbitrary integer. Note that if $(k, 1 - k)$ is a solution with $k > 0$, then taking $t = 1 - k$, $k = 1 - t$, so $(1 - t, t)$ is solution. Thus by symmetry $(k, 1 - k)$ is a solution for any integer.