This problem doesn't have spherical symmetry, so there's no way to use <PERSON>'s Law directly. (If I understand what you wrote correctly, you appear to be implicitly assuming that 0 charge enclosed in a region implies that $E = 0$ on its boundary, but this is only the case if there is sufficient symmetry; in general, all <PERSON>'s law says is that the flux through the boundary of some region is equal to the charge enclosed.)
Like you say though, you can treat the problem as the superposition of a sphere of uniform density $\rho$ and a smaller sphere of uniform density $-\rho$, then use <PERSON>'s Law on each of these systems separately, since they do have spherical symmetry (albeit with different origins).
Hope this helps. Happy to elaborate further if necessary.
Clarifications:
Superposition is just the idea that if you have two charge distributions $\rho_1$ and $\rho_2$ that alone create electric fields $E_1$ and $E_2$, then the charge distribution $\rho_1 + \rho_2$ will have electric field $E_1 + E_2$. 903
This may seem like a trivial statement, but as you can see in the above problem it turns out to be quite powerful (and yes, here $\rho_1$ and $\rho_2$ correspond to two spheres which overlap in the region with zero charge, since $\rho_1 + \rho_2 = \rho -\rho = 0$ here).
Spherical symmetry occurs when all directions from the origin are indistinguishable in a system. So a uniformly charged sphere has spherical symmetry, but in the above problem there isn't spherical symmetry since the $y$ direction is distinguishable from the other directions (since there is a hole in the charge distribution.
If you have spherical symmetry, then you can assume that the electric field at radius $r$ from the origin points radially and only depends on $r$ (i.e., not on $\phi$ or $\theta$). This allows you to convert the surface integral in <PERSON>'s Law to the form $$\int_S \mathbf{E} \cdot \mathbf{da} = 4\pi r^2|E|,$$ which then allows you to calculate the electric field directly.
But it's really important to realize that this only applies when there is sufficient symmetry (which means spherical symmetry here, but could also mean cylindrical or planar symmetry in other problems). Otherwise, the surface integral cannot be simplified further, so you have to be more clever, which in the case of the above problem means using superposition to reduce the problem to two which do have sufficient symmetry to simplify the surface integral. 903