Does the weight of a phone increase by a few mg when your phone is fully charged?

It is the question needs some detailed explanation. Coz, It depends upon various things like the Mass of an electron or something.

The General Answer to this question is,

         Yes, the total mass of a battery increases when the battery is charged and decreases when it is discharged.

The difference boils to Einstein's $E=m{c}^2$ that follows from his special theory of relativity. Energy is equivalent to mass and $c^2$, the squared speed of light, is the conversion factor.

I would omit the scenario I. If the lithium is leaking from a battery, or if any atoms (and it's the nuclei that I am talking about) are moving in or out, the mass of the battery is obviously changing by the mass of these nuclei (or whole atoms). That probably doesn't need an extra explanation. So we will continue with the scenario II in which the atoms inside the battery are only rearranged into different configurations or different molecules but the identity and the number of the nuclei inside the battery is constant.

Let me just emphasize that the energy can't be calculated from masses of the electrons. Electrons are not lost when a battery is discharged. If a battery is losing electric energy, it doesn't mean that it's losing the electric charge! They're just moved from one electrode closer to the other and it's just the motion through the wire stretched between the electrodes (and the electric field inside the wires) that powers the electric devices. But the whole battery is always electrically neutral; because it contains a fixed number of protons, it must contain a fixed (the same) number of electrons, too.

Instead, the energy difference really boils down to different electrostatic potential energies of the electrons relatively to the nuclei. One could say that when a battery is being discharged, its electrons are moving to places that are closer to the nuclei, perhaps other nuclei, in average and the modified interaction energy affects the amount of energy=mass stored in the electromagnetic field.

(There are also interaction energies of electron pairs and kinetic energies of electrons – $m_e{c}^2(1/\sqrt{1-v^2/c^2}-1)$ – but let me simplify it by the potential energies of protons-electrons which are dominant and have the right sign. Well, it could actually be pedagogical to borrow the electrons' kinetic energies as the source of the mass difference because for them, we immediately see that the relativistic mass is $m_e/\sqrt{1-v^2/c^2}$ which depends on the velocity and the average squared velocity of the electrons depends on how we arrange the molecules i.e. on whether or not the battery is charged.)

Yes, the change of the mass is pretty much negligible and can't be measured by current scales.

For example, Chevrolet Volt has batteries that may store 16 kWh. Multiply it by 1,000 and 3,600 to get the value in Joules; divide it by ${10}^{17}$ which is (approximately) the squared speed of light and you get the mass difference in kilograms. It's about

$$16\times 1,000\times 3,600/{10}^{17}=0.6\times {10}^{-9}$$

That's half a microgram – for this huge Chevrolet Volt battery. One can't really measure it this precisely because pieces of the battery evaporate, the battery may absorb some dust, humidity etc. The mass difference above is comparable to the mass of a water droplet of diameter 0.1 mm or so. Even the national prototype kilograms

http://en.wikipedia.org/wiki/International_Prototype_Kilogram#Stability_of_the_international_prototype_kilogram

have masses that differ from the mass of the international prototype kilogram by dozens of micrograms. From 1900, each of them has changed by a dozen of micrograms. So the unit of "kilogram" isn't even defined "internationally" with the accuracy needed to distinguish the masses of the battery before and after. However, it's plausible that a fancy device could measure the mass difference more directly; the difference of the mass isn't infinitesimal, after all. But when you're touching the electrodes, you must be careful not to scratch them, not even a little bit, and not to allow the paint to evaporate when the battery gets warmer, not even a little bit, and so on.

The measurement problem would become much more manageable with a nuclear battery, of course. ;-) If you let some uranium decay by fission, it creates lots of energy (e.g. in Temelín) and the mass $m=E/c^2$ decreases by 0.1 percent or so. If you had a thermonuclear power plant running on hydrogen, the products of the fusion would be about 1% lighter than the hydrogen at the beginning. That would of course be measurable in principle. Nuclear energy is much more concentrated (about 1 million times higher densities in Joules per kilogram: 1 MeV per nucleus i.e. per atom) than the chemical energy (and batteries run on chemical energies: about 1 eV per atom) so the relative change of the mass would be 1 million times more significant, too.

A hypothetical (science-fiction) matter-antimatter fuel producing energy from complete annihilation of matter against antimatter (note that both of them have a positive $m$) to electromagnetic waves (quickly converted to heat etc.) would lower the original mass of the solid material $m=E/c^2$ down to zero i.e. by 100%; the objects that would absorb the heat (or the energy partly converted to more useful forms) would get heavier by the same amount.