Where does the charge on an electrode, responsible for the formation of a double layer once submerged in an electrolyte, come from?
This can be answered on more than one level. Where did the word "electrode" come from, to begin with? Supposedly it is due to the fact that you apply some electric potential to that metal needle (stuck into the brain of some creature or other electrolytic medium), and that's why the electrode gets charged.

Now what if we apply no potential? Well, for example, if two pieces of different metals are in contact, they would form a galvanic couple and develop some potential on their own, resulting in galvanic corrosion.

But wait, what if there is just one metal in the electrolyte? It turns out that some contact potential would develop even then. As the link says:


  Electrode potential appears at the interface between an electrode and electrolyte due to the transfer of charged species across the interface, specific adsorption of ions at the interface, and specific adsorption/orientation of polar molecules, including those of the solvent.


Think of a metal in a distilled water (which, BTW, is a poor electrolyte). Inevitably, a tiny portion of metal would dissolve, for such is the nature of chemical equilibrium: it is almost never shifted all the way to one side. Now, that metal would be in the form of cations, and the extra electrons would stay in the bulk, giving it a negative potential (not so tiny, because the electric forces are quite powerful). And if we consider other possible effects, especially if the water is not distilled but contains some ionic species, then the resulting potential on the metal can be pretty much anything (and not necessarily negative).

All in all, a random piece of metal in a random electrolyte will most likely have some potential difference with the electrolyte and hence form a double layer.