Because $\nabla \times \nabla \psi = 0$, we can transform the vector potential $A \longmapsto A + \nabla \psi$, without changing the magnetic field. Is the reason we specify $\nabla \cdot A$ in the gauge theory, because $\nabla \cdot \nabla\psi\ne0$? Thus, we always can find a function $\psi$, such that $\nabla \cdot A$ equals to whatever we want.
A bit more elaborated:
Let's say I found $A$ and $\phi$, and $\nabla \cdot A \ne 0$. In principle, nothing stops me from finding a function $\psi$, such that $\nabla \cdot (A + \nabla \psi)=0$ (Coulomb gauge). But now my scalar potential will be modified. Then from Gauss' law: $\nabla \cdot( \nabla\phi+\frac{\partial \nabla\psi}{\partial t}- \frac{\partial }{\partial t}(A + \nabla \psi))=\nabla \cdot( \nabla\phi+\frac{\partial \nabla\psi}{\partial t})$. Thus, the new 4-potential in the Coulomb gauge $(\phi,A)\longmapsto (\phi+\frac{\partial \nabla\psi}{\partial t},A + \nabla\psi)$. So, the freedom of choosing the divergence stems from the freedom of choice of $\nabla \phi$.