I've been thinking about this for the past couple of days. I apologize if my explanation isn't very clear.
I have already seen derivations of this, but I'm still not satisfied.
In the derivations of Coulomb's law from Gauss's law that I've seen, we take a spherical shell of radius $r$ around a point charge and calculate the electric flux through it.
$$\oint\limits_A \vec{E}\cdot d\vec{A} = E\cdot 4\pi r^2 = \frac{Q}{\epsilon_0} \Rightarrow E = \frac{Q}{4\pi\epsilon_0 r^2}$$
What is assumed here, however, is that the electric field is perpendicular to the surface and has the same magnitude at every point on the spherical shell. Gauss's law does not state that explicitly, though, but Coulomb's law explicitly gives us the magnitude and direction of the force between two charges (and thus the direction of the electric field of a single charge).
Am I correct in thinking that, in addition to Gauss's law, we also need to state (as another law) that the electric field of a point charge points radially outwards (or inwards), and that its magnitude only depends on the distance from the point charge?
Another way to formulate my question would be: is this "other law" somehow hidden in Gauss's law?