All the electrons in the metal obey quantum mechanics at the microscopic level, regardless of whether it is the bulk or the surface. However, depending on the system you are studying, and the conditions you have created, you can safely employ a semiclassical description of electron motion. For most typical metals of macroscopic scale, the single-particle semiclassical description works well (Drude model is the simplest). My explanation below relies on this assumption:
Metals have half filled bands; or in other words, the chemical potential lies in between a band. As a result, the electrons near the chemical potential can move around the metal, while the electrons that are much deeper, i.e. way below the chemical potential, stay bound to the positive ion cores. If you introduce an excess negative charge, the extra electrons will go into the half filled band, and consequently the chemical potential will rise slightly; the band will still be half filled. You can safely ignore filling up of this band by the excess electrons. I am saying this because even if you introduce one extra electron per atom, and you have an Avogadro number of atoms, you will get some ridiculous values of net excess charge $6\times10^{23}\times1.6\times10^{-19}=9.6\times10^4 C$. In the end you have a system which is still like a metal except there will be a net charge. Since the extra electrons lie in a half filled band, and lie close to the chemical potential, these electrons will also be delocalized. So yes, like Ondřej Černotík was implying, the electrons will move around randomly such that the net vector sum of their velocities will add up to zero.
To sum up I would like to say that there are indeed two classes of electrons: (1) moving (delocalized) (2) bound. The delocalized electrons will exist on the surface as well as in the bulk. The excess electrons, however, will only exist on the surface. I think that can be explained classically by minimization of capacitive energy $E = Q^2/2C$. The capacitance of a cylindrical shell is proportional to the radius, i.e. $C \propto R$. Therefore it is energetically favorable for the electrons to be as far away from the center of the object.
By the way, all this band description in the second paragraph is simply to make the point that the excess electrons will be delocalized, i.e. they fall in class (1) of electrons. That explanation simply supports my claim that electrons are moving around randomly.
