First, since both the electrostatic field and the integral are additive, it is (intuitively) enough to see that the law works for a point charge either inside or outside the surface. We can imagine adding all of the charge in the final configuration little by little -- if Gauss' law holds for each small increment, it is also going to hold for the sum.
So let's imagine a point charge and see how its Coulomb field (which has a nice simple shape) contributes to its surface integral. In particular, let's consider the part of the surface that lies within a thin cone with the point charge at its apex. The entire integral is then the sum of the contributions for enough such ("infinitesimally thin") cones to cover all directions we can look at the point charge from.
In the general case, if we make the cone thin enough it will look like simply a ray when we look at it from the scale of the surface. We can ignore the cones/rays that are ever tangent to the surface; they are too few to make a net contribution when we go to the limit. So by assumption each cone will cross the surface a well-defined number of times -- an odd number if the charge is inside the surface, and an even number if the charge is outside the surface.
Now each crossing between the cone and the surface contributes to the surface integral by precisely the same magnitude (though with different signs according to whether we're going into or out of the surface), no matter where this crossing happens. Since we're going to the limit, at the point of crossing the cone looks like a cylinder and the surface looks like a plane. If the crossing is far form the point charge, the area of the surface in the intersection is larger, but the field is weaker by exactly the right factor to cancel that out -- here it is crucial the the field is inverse square, it wouldn't work for any other shape of the field. The area of the intersected surface is also larger if the crossing happens at an oblique angle, but that is canceled out exactly by the cross product in the integrand.
Now if the charge is outside the surface, every cone crosses the surface an even number of times, which cancel out each other in pairs -- so each cone contributes zero to the total surface integral.
On the other hand, if the charge is inside the surface, there is one more outgoing crossing than incoming for each cone -- so each cone contributes to the surface integral in proportion to its solid angle. All the infinitesimal cones taken together have solid angles that add up to $4\pi$ steradians, so the total surface integral is the same no matter what the shape of the surface and where inside it the charge is located. It's obviously proportional to the strength of the charge too, and the various proportionality factors are then subsumed into the $\epsilon_0$ constant by definition.