When you put +ve charge on a conductor, you are really removing the same amount of -ve charge, because only the electrons move.
Gauss' Law assumes that charge is infinitely divisible, and can be spread uniformly throughout a volume or over a surface. This is a good approximation when the charge is on the order of $1 \mu C$, corresponding to about $10^{13}$ electrons. Then volume and surface charge densities $\rho$ and $\sigma$ have meaning.
However, when the charge is made up of a small number of electrons - and even more so when it is only one electron - these quantities do not have any meaning unless they are averaged over time. For the same reason, if the charge on the conductor is an excess or deficit of a small number of electrons, the electric field may not be zero at all points inside, because the excess charge is not spread uniformly over the surface.
Because of the random high-speed motion of the conduction electrons throughout the conductor, the electric field $E$ inside it may not be very well defined at all when the excess/deficit charge is so small, and will fluctuate with a standard deviation proportional to $\frac{1}{\sqrt{n}}$ where $n$ is the excess number of excess/deficit electrons.
Even when there are $10^{13}$ excess electrons, no particular group of $10^{13}$ electrons stays on the surface while the original conduction electrons stay inside. All of the electrons are identical and move around equally, and it is only on average that an excess of electrons will be found near the surface. As more electrons are added or removed, the region in which the excess or deficit of electrons is likely to be found - and in which the electric field is not close to zero - will get nearer and nearer to the surface.
If you add or remove charge, there is always a redistribution of the average charge, even when a single electron is added or removed, because the electrons are moving around randomly at high speed. They are not fixed to the surface.