Do we fix divergence of the vector potential $A$, because $\nabla \cdot \nabla \psi \ne 0$? 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$.
 A: Gauge freedom is the freedom to transform $\mathbf{A} \to \mathbf{A}' = \mathbf{A} + \nabla \psi$ and $\phi \to \phi' = \phi - \partial \psi/\partial t$ for any scalar function $\psi$.  (Note the slight difference from your expressions.)  If we want to demand that $\nabla \cdot \mathbf{A}' = 0$ (Coloumb), this boils down to being able to find a function $\psi$ such that $\nabla^2 \psi = -\nabla \cdot \mathbf{A}$.  Since we know that there is always a function $\psi$ that satisfies this equation, the condition $\nabla \cdot \mathbf{A}' = 0$ is always realizable via a gauge transformation. 
That said, there are plenty of other gauge conditions out there that we could impose that do not lead to $\nabla \cdot \mathbf{A}' = 0$.  Other common choices include $\nabla \cdot \mathbf{A}' + \partial \phi'/\partial t= 0$ (Lorenz gauge), $\phi' = 0$ (temporal gauge), and $\mathbf{A}' \cdot \hat{n} = 0$ for some unit vector $\hat{n}$ (axial gauge).  All of these are realizable, in the sense that given an arbitrary $\mathbf{A}$ and $\phi$, there always exists a function $\psi$ such that the transformed potentials satisfy the desired condition.
So it's not accurate to say that we must impose Coulomb gauge because we have gauge freedom.  It's more accurate to say that we are allowed this choice because of gauge freedom, and that gauge freedom allows us many other choices as well.
