Why it is colder in mountains, at high altitudes? The conventional answer is to say that "lower temperature follows from lower pressure because temperature is average molecular energy (average speed)". For instance "Temperature is a measure of kinetic energy (how fast things are moving around). At lower altitudes...there are more air molecules than at higher altitudes" and at Quora "Greater space between molecules means less intermolecular collisions, which means lower average kinetic energy, which means lower temperature."
Do you see how they silently substitute speed of a particle (average energy) with number of collisions (particles)? Why? If I look at the average energy, N seems to cancel out, leaving expected $E_{avg} = \sqrt{mv^2 \over 2} = 2/3kT$ independent of the "number of collisions". Why do the explainers resort to such tricks and why cannot you simply explain it by saying 

as molecules jump higher, they loose energy/speed due to gravity. This
  results in molecules slower at heights and therefore you have lower
  temperatures at the heights, boy.
Once the molecule falls back to the Earth, gravity accelerates it,
  recovering all the energy, and molecule regains it normal
  energy/temperature at the lower altitues.

This seem to give the whole picture and in the first principles, without entailing the pressure. Is such explanation legitimate, as alternative to the pressure-based one? I cannot find it anywhere. 
 A: An atmosphere in absolute equilibrium in fact is isothermal (see below for more detailed analysis of your cannonball). However, if the atmosphere is mixed by wind, gas expands and contracts adiabatically. If the mixing is fast enough, it obeys relatively well the adiabatic invariant, which multiplied by suitable form of ideal gas law ($(T/(pV))^\gamma = 1/(\nu R)^\gamma = const$) results in
$$pV^\gamma = const \Rightarrow$$
 $$\frac{T^\gamma}{p^{\gamma - 1}} = const $$
Thus, if the pressure decreases with altitude, temperature also decreases, assuming the air is adiabatic.

So, what about the cannonball?
Instead of cannonballs moving in 3d space, lets just consider 1d upwards shooting cannon. In your example, you made a slight mistake. Instead of shooting a single cannonball, you should have shot many and with velocities according to Bolzmann distribution - the probability of shooting some cannonball with velocity $v$ is proportional to $e^{-E/kT} = e^{-mv^2/2kT}$ (ideal gas obeys exactly the same probability relation). You correctly noticed that a cannonball at $h = 0$ has less kinetic energy at height $h = h'$, which led to your result. But you didn't take into account that only cannonballs with high enough initial energy can reach an altitude of $h'$, thus "filtering" out the low energy balls. This effect conversely increases the average energy of the cannonball - which happens to exactly compensate the effect mentioned above.
More mathematically - in order to get the distribution of velocities at some other height, let's first ask what is the probability of reaching a maximum altitude of $h_{max}$. From energy conservation, $mv_z^2/2 = mgh_{max}$ (only the $z$ component is important). Thus the probability is simply proportional to $e^{-mgh_{max}/kT}$. If we are sitting at height $h'$, the probability distribution for a cannonball to rising for another $\Delta h$ is $p \propto e^{-mgh_{max}/kT} \propto e^{-mgh_{max}/kT}e^{-mgh'/kt} = e^{-mg(h_{max} - h')/kT} = e^{-mg \Delta h/kT}$ (I just multiplied rhs by a constant factor). Keeping in mind that $mg \Delta h = mv'^2/2$ is also the kinetic energy at that height, we conclude that the velocity distribution and thus the average kinetic energy are the same at different heights.
A: 
Why it is colder in mountains, at high altitudes?

One answer is that mountains on Earth aren't all that tall. An impossibly tall mountain would see temperatures vary with altitude as depicted below.

(source: weather-climate.org.uk)
Tall as it is, even Mount Everest doesn't extend into the stratosphere. This is a question about the lowest layer of the atmosphere, the troposphere. Temperature in the troposphere generally (but not always) decreases with altitude because of four key factors:

*

*The incoming energy from the Sun is predominantly in the visible and near infrared, which represents one of the few windows in which the atmosphere is fairly transparent.

*The outgoing energy that balances the incoming energy is in the form of thermal infrared radiation. The atmosphere is quite opaque in this frequency region thanks to the trace greenhouse gases in the atmosphere.

*The air in the troposphere is always in motion. The name "troposphere" means just that, the constantly turning part of the atmosphere.

*Air is a very poor conductor of heat.

All four are important. Temperatures rise with increasing altitude in the stratosphere and thermosphere because those portions of the atmosphere absorb the high frequency components of the Sun's output. The greenhouse effect is also very important. A dwarf planet in the outer reaches of the solar system with a pure helium atmosphere would have a nearly isothermal atmosphere because helium is not a greenhouse gas. Finally, mixing is important. For example, Los Angeles has serious problems with smog because temperature inversions often set up that keep the air around LA stagnant. The short mountains around Los Angeles are often warmer than is Los Angeles itself.
The latter two reasons mean that the troposphere is approximately adiabatic. Parcels of air expand and cool adiabatically as they rise, contract and warm adiabatically as the fall. An adiabatic atmosphere is the steady-state condition for an atmosphere that is warmed from below and cooled from above. It is also a local maximum with regard to entropy.
The global maximum with regard to entropy would of course be an isothermal atmosphere. A ten kilometer tall thermally insulated cylinder of gas would evolve toward an isothermal temperature rather than the (roughly) linear lapse rate we see in the Earth's troposphere. So why don't we see that in the Earth's atmosphere? The answer is that the four factors listed above keep the Earth's atmosphere very far from thermodynamic equilibrium. The Earth's atmosphere is the canonical example of non-equilibrium thermodynamics.
As an extreme example, consider Venus. Venus's atmosphere isn't in constant flux the way our troposphere is, and very little sunlight reaches the surface of Venus. However, almost all of Venus' atmosphere is in the form of greenhouse gases. The extreme greenhouse effect on Venus creates the conditions that enable an adiabatic temperature profile, which is why Venus' surface is so very, very hot.
A: 
as molecules jump higher, they loose energy/speed due to gravity. This results in molecules slower at heights and therefore you have lower temperatures at the heights, boy.

Molecules do not jump up, they scatter off each other every which way. The difference in gravitational energy within the nanometers  of the molecule's path before a scatter on another molecule is tiny with respect to the electromagnetic forces which define the scatters. 

Once the molecule falls back to the Earth, gravity accelerates it, recovering all the energy, and molecule regains it normal energy/temperature at the lower altitutes.

by a few nanometers of difference in altitude from scatter to scatter.
So your statements are irrelevant.
The change in temperature with pressure in a gravitational field is called the lapse rate and it is affected by the composition of molecules and is defined within thermodynamics. Thermodynamics is a mathematical model of the behavior of matter in bulk, validated in its region of validity, i.e. it has laws and derived formulas that have not been falsified within most of the phase space . A simplified description can be found here.
A: Imagine wind blowing along a plane with the air by the ground all a nice and steady temperature.  Now this wind encounters a mountain range, so is forced upwards.  The pressure is lower at higher altitude since there is less remaining atmosphere above it.
The temperature of gas decreases when the pressure is lowered, which is why this same air gets progressively colder as it moves up the side of the mountain range.
To make you feel better about the energy balance, consider that this expanding gas does work on its surroundings.  It now has a higher volume, that it got by pushing on the air around it, which was at some finite pressure.  That represents work, which is one way to justify the lower thermal energy.
Ignoring any exchange of heat between the air and the mountain (which is largely valid for the bulk of the reasonably fast moving air since heat exchange can only happen at the boundary), the same amount of air at a higher volume actually makes a little more wind, in addition to the mountain acting as a constriction, requiring even faster wind to move the same original mass of air.
A: The air becomes colder because of the ideal gas law, $PV=nRT$.
where $P$ is pressure, $V$ is volume, $n$ is the number of moles of the gas, $R$ is the ideal gas constant, and $T$ is the temperature of the gas in Kelvin.
If we rearrange $PV=nRT$, we can solve for $T$. By looking at $T=\frac{PV}{nR}$ you can see that reducing pressure will reduce the temperature. $T\propto P $.
Because at higher altitudes there is less air to pressurize the air below it, the pressure drops as you go higher. If you look at this image, you can visualize this.

Credit to Indiana University for the visual.
And another reason why:
Keep in mind that in order to be heated by the sun, something has to absorb the solar radiation. Some of the solar energy is absorbed by the air, but most of the energy is absorbed by the ground. The ground, in turn, heats the air by either convection or, to some extent, directly by conduction. 
As the altitude above ground level increases, so does the distance the heated air has to travel to heat the upper atmosphere. Along the way it has to pass only slightly cooler air, which steals some of the energy from the rising warmer air. Eventually there isn't enough warmer air left to heat the upper atmosphere, so it stays cool.
Related or interesting:
Georgia State University's physics database (Heat & Thermodynamics)
Why is temperature less at higher altitudes? (P.SE question)
Why is colder with higher altitudes? (Google search)
The Ideal Gas Law explained, Crash Course (YouTube video)
The Ideal Gas law (Chemwiki, they have a pretty good explanation.)
A: I guess we all agree that a cannonball does not get cold when flying upwards, it loses kinetic energy, not heat energy. Why would ascending air not do the same thing? 
So equivalently to an ascending cannonball we get:
When one molecule in a rising column of air bounces upwards, it loses kinetic energy while moving upwards. That loss of kinetic energy is a loss of kinetic energy of the column of air, not a loss of heat energy of the column of air.
Let's consider a single lead molecule, dropped from 10 km altitude. It will sink down very slowly, heating the surrounding air while descending. 
And a helium atom let free at sea level would slowly ascend absorbing energy from the surrounding air while ascending.
