The electric field used in Gauss's law is not just the electric field from the interior charge distribution. It may contain contributions from exterior sources. Usually, we do assume that there are no exterior sources, which is what allows us to impose symmetry considerations.
Why are we able to do this? Because Maxwell's equations are linear, and as such, the sum of two solutions to Maxwell's equations is itself a solution. Hence, you can consider the exterior and interior charge densities separately. You can calculate the fields separately and then add them up at the end.
Here's a mathematical way of looking at it. You have Gauss's law in integral form:
$$\int_V \frac{\rho}{\epsilon_0} \, dV = \oint_S E \cdot dS$$
Linearity of Maxwell's equations means that you can split up $\rho = \rho_\text{int} + \rho_{\text{ext}}$ and the same for $E$. The two parts must separately obey this equation. So that means we have
$$\begin{align*}
\int_V \frac{\rho_\text{int}}{\epsilon_0} \, dV &= \oint_S E_\text{int} \cdot dS \\
\int_V \frac{\rho_\text{ext}}{\epsilon_0} \, dV &= \oint_S E_\text{ext} \cdot dS
\end{align*}$$
But $\rho_{\text{ext}} = 0$ everywhere in $V$, so the second RHS integral must be zero.
When we do Gauss's law problems, we implicitly look at the $E_\text{int}$, the field generated by charges internal to the volume. Any external field and charges can be separated out in this way, so that the symmetry of the field generated by internal charges is still manifest, allowing us to compute the field magnitude thanks to that symmetry. It's true that, strictly speaking, we can't draw any conclusions about the total $E$-field without some information about exterior charges or fields, but by linearity, we know that our field from the internal charges will never be affected by such information.
In an attempt to be brief: The big thing to remember is that the flux is also proportional to the area (technically, the surface integral of the field over the area). Crudely speaking, the side of the enclosed surface with exiting field lines are further away from the external charge than the side with "entering" field lines, and the surface area increases by $r^2$ (remember the formula for the surface area of a sphere). Gauss's Law is just a mathematically precise way of stating this compensation.
(Image source: http://www.ux1.eiu.edu/~cfadd/1360/24Gauss/Gauss.html)
Best Answer
Gauss' Law says $\iint_S \mathbf{E} \cdot \mathbf{dA} = Q/\epsilon_0$ whereas the total vector area is $\iint_S \mathbf{dA}=\mathbf{0}$ for some closed surface $S$. The total vector area is taking vector sum of all the differential area vectors that are normal to the surface, whereas $\iint_S \mathbf{E} \cdot \mathbf{dA} = Q/\epsilon_0$ is taking the dot product of the electric field and the differential area vector.
Let's use a sphere of radius $R$ centered at the origin as an example. Its clear that $\iint_S \mathbf{dA}=\mathbf{0}$ since, for every point on the sphere, the normal vector of that point cancels out with the point opposite it on the sphere. Therefore, $\iint_S \mathbf{dA}=\mathbf{0}$.
Now suppose there's a charge $Q$ at the origin. The electric field and the normal vector will be parallel at every point on the sphere, so the symmetry of the problem means $\iint_S \mathbf{E} \cdot \mathbf{dA} = EA$ where $E$ and $A$ are the electric field and surface area of the sphere respectively.