Electrode potentials at interfaces?
There are a bunch of of sub parts to these questions; let me see if I can tease some of them out.
Why does a potential difference occur at an interface?
The easiest way to answer this question is through thermodynamics.  If we consider the situation of a reactive metal rod (e.g. magnesium) being exposed to water, the reaction $$\ce{Mg -&gt; Mg^{2+} + 2 e-}$$ is favorable.  In other words, the $\Delta G$ for this reaction will be less than zero.  I've done nothing more than summarize the website you reference in your question, which does a nice job at describing what happens when a piece of metal comes in contact with water, so I don't feel the need to repeat that work.  We then get to your next question:
Why is a second phase required to generate a potential difference?
If we have a universe that consists just of magnesium, then there would be no place for the above reaction to occur.  In this trivialized case, there is no driving force to make magnesium give up its electrons.  That doesn't mean it would not happen, only that any dynamic equilibrium that is established would highly favor the pure metal.  The meat of question one, then, is (may be?):
Why doesn't a potential difference between a metal and gas occur?
Actually it does.  There's an interesting paper (which is behind a paywall if you are not at a university that subscribes to this journal) that describes the measurement of potentials across metal/gas interfaces.  The challenge in studying metal/gas potentials is the ability of controlling this potential externally.  With the metal/liquid scenario, an electrochemist (or budding electrochemist) can add another electrode to the solution and apply a potential between the electrodes.  It's much harder to do the same thing with a gas.  (Well, technically it's *not harder to connect two electrodes to one another and hold them in air, but the redox work functions, resistance and capacitance issues that arise in gas-phase electrochemistry make this a really challenging feat.)
The paper I reference above uses chemisorbed species that have active IR or Raman vibration modes to measure the surface potential using spectroscopy and something called Stark tuning (not the best reference, but it's also not behind a paywall) which states that the vibrational frequency of an harmonic oscillator is proportional to an applied electric field.  Not many metal/gas interfaces have been explored using this method, but those that have display surface potentials fairly close to 0 vs. SCE or 5 eV vs. vacuum.
What about the rest of the stuff in solution?
Back to the metal/liquid scenario, the last part of your first question asks about other ions in solution.  They most definitely play a role in defining the potential of a metal in solution.  In order to accurately predict electrode potentials, one must know concentrations and possible reactions (including states of matter) for all species present.
What about question 2?
I'm afraid question 2 might be based on the false premise that we can measure the potential of an electrode in the absence of anything else (liquid, gas, ions or molecules).  When electrochemists refer to a 'half cell', they have in mind both the reduced (in this case, metal electrode) and oxidized (metal ions) forms of a redox couple contained within the same system.  (Think about a beaker with a copper wire placed in it and the beaker is filled with a solution containing 0.1 M $CuCl_2$.  That half-cell or system has a given potential based upon (primarily) the standard reduction potential of $Cu^{2+}$ to $Cu$ and the concentration of $CuCl_2$.  If I have misread your second question, please edit and I will update my answer as needed.