Void's answer relies on the mathematical knowledge that the Laplace equation has one unique solution when we specify the boundary conditions. Here I'll try to give a more intuitive for the question. Hope it helps.
This question is best understood in terms of the potential defined as,
$$\vec{ \nabla} \phi = -\vec{E}.$$
As you mentioned we know that the field inside the metal has to be zero, since otherwise, the free charges inside the metal would move. This entails that the potential energy inside the metal (and on its surface) is constant. You can easily see this because you can move from any point in the metal to any other point without seeing any field, and hence the change in the potential energy is zero. Let's call the potential energy of the metal $\phi_0$.
Now your main question. How do we know that the electric field inside the cavity (which is not part of the metal) is zero. We can answer this question by showing that the potential energy inside the cavity has gotta be constant and equal to $\phi_0$.
Pick any point, $P$, inside the cavity. We prove that the potential of this point $\phi(P) = \phi_0$ by contradiction. Assume first that $\phi(P)>\phi_0$ ($\phi(P)<\phi_0$). Then look at the paths connecting this point to the surface. As we move along any of these lines, the potential changes from $\phi(P)$ to $\phi_0$, hence on all these lines there must be regions where the electric field is points outwards (inwards). This however cannot be true. Since if we looked at a surface that connect all these regions, the surface integral of the electric field is not zero, which from $\vec{\nabla}\cdot E = \rho/\epsilon_0$ means that the region contains electric charges, which we know is not true. We must then conclude that $\phi(P) = \phi_0$. But $P$ can be any point really, so all the points inside the cavity must have potential of $\phi_0$. Hence the electric field is zero inside the cavity.
Edit (1): Elaboration on the method.
Allow me to maybe explain this better. I'd actually wanna know if this doesn't hold water. For any point $P$ inside the cavity consider a sphere surrounding that point. For our proof by contradiction let's focus on the assumption that $\phi(P)>\phi_0$ first. For each point on the sphere we ask what is the gradient of $\phi$ at this point. If the gradient is pointing inwards we do noting. However if the gradient is pointing outwards or zero we do the following. We connect the point $P$ to that point on the surface with a straight line, and further extend this straight line until it reaches the metal. Now since $\phi(P)>\phi_0$ somewhere on that line the gradient of $\phi$ must be pointing towards $P$ and away from the metal. So what we do is deform the sphere such that it intersects the line at this point. Then we repeat this process for each point on the surface. The resultant surface would be a surface that has the gradient of $\phi$ pointing inwards at all points, hence the electric field pointing outwards at all points. Thus the surface integral of the field would be non-zero. This would mean there must be some enclosed charge, and hence the contradiction. This would mean that $\phi(P)$ cannot be bigger that $\phi_0$. We can do the same thing if $\phi(P)<\phi_0$. Thus $\phi(P)$ can only be equal to $\phi_0$.
Edit (2): This uses more than $\vec{\nabla} \cdot \vec{E} = 0$.
Sorry this is getting long. I wanted to address more explicitly the claim that this only uses $\vec{\nabla} \cdot \vec{E} = 0$. It doesn't, here is why. If that was the case then I would be able to proof the same thing had for example we replaced the metal shell with a dielectric such that the inner surface of the dielectric is not an equipotiential surface. In this case the electric field still has a zero divergence since there is still no charges inside the cavity. However this proof would fail in this case. Let the potential on the inner cavity of the dielectric range from $\phi_1$ to $\phi_2$ with $\phi_2 > \phi_1$. Then one cannot show that the potential is constant inside the cavity. To be exact, you cannot show that $\phi(P)$ cannot lie between $\phi_1$ and $\phi_2$. This is because some of the lines coming out of $P$ and ending on the inner surface will have a net decrease in potential, while others would have a net increase in potential. Thus I cannot argue that a surface surrounding this point will have a net electric field surface integral. The proof fails even though the divergence everywhere in the cavity is zero for the dielectric case. So this proof relies on two things:
- $\vec{\nabla} \cdot \vec{E} = 0$
- That the inner wall of the cavity is an equipotential surface.
And indeed these two conditions should be sufficient.