Good question! I watched Lewin's lectures a few years ago and distinctly remember this explanation as being unsatisfactory. It's one of the very few places where he "cheats" and skips a few steps.
The missing step is the existence/uniqueness theorem. We know, from Lewin's argument, that the total charge on the inside surface is zero, and the boundary condition is that there can be no field at the Gaussian surface itself. Moreover, we already know there exists a solution to this problem (i.e. zero charge density everywhere on the inside). So that has to be the unique solution.
This is still cheating a bit, because we're ignoring the influence of the outside surface. We can redo the argument more carefully: we keep the same boundary condition, but demand total charge $Q$ on the outside surface and zero total charge on the inner surface. Again, we already know there exists a solution: it is the charge distribution on the outside surface of a solid (non-hollow) conductor, which guarantees zero field everywhere inside. So this must be the unique solution.
As a nice corollary, this implies that the outside of a conductor never knows anything about holes in the inside: in ideal electrostatics, there is no way of telling if a conductor is hollow.
