You ask two question. it is always better to restrict a post to only one accurate and narrowed enough question. I will not provide a full review of how did the origin of tetrapods occur. I just give some critics on you question give some words about the evolution of lungs, discuss your comparison with "breathing on the moon" and answer your question concerning the origin of genetic variation.
How did fish evolve the ability to breathe on land?
This question is way too broad, you should narrow it down. You say that this evolution is impossible but you should provide some argument so that we can discuss them. For the moment there is not much to discuss about. The only thing one could si to review tons of article concerning the evolution of tetrapods. I bet you're interested in the evolution of lungs during at the origin of the lineage of the tetrapods. If so… In short, swim bladder and lungs are homologous organs. According to this that at the time tetrapods-like animals evolved, this organs was used to gulp air in oxygen-poor environment. This organs then evolved into various forms of lungs as we know them today in terrestrial and none terrestrial vertebrates. This organ also further evolved in order to control the buoyancy. Note: Several popular sources gives different informations. One would need to go into some articles in order to make sure of details such as "were this organ already used to control buoyancy before the speciation of the tetrapods?".
Here is a simple source that you may like
You say that evolving abilities to breath in the atmosphere for tetrapods is like evolving abilities to breath on the moon in humans. Well there are several differences that should be considered that make the moon really not a pleasant place to live! The temperature for example spans between 100K and 373K according to this wiki! But let's forget about these other ecological factors. One big difference is that humans do not live in an environment that offers a gradient from earth atmosphere to moon atmosphere while first tetrapods-like animals lived in such a gradient. Also, when you talk about human, it feels like you consider the wrong time-scale. It probably took quite a lot of time to evolve from fish-like to totally terrestrial tetrapods.
You might want to have a look to this interesting post. Life apparently independently emerged out of water at least 9 times.
"How does an organism gain the new information necessary to get those land breathing or moon breathing adaptions, from a genome that doesn't already have such an ability encoded in its genetic morphology in the first place?"
If I understand your point correctly one could rephrase your question into:
"I understand the process of Natural Selection (NS). It selects for some already existing variants but what process creates the variation from which NS makes its selection?
And the answer is: Mutations. In the narrow sense (in order to keep it easy), a mutation is a change in a genetic sequence. Such change typically occur during the meiosis, process that occurs in all sexual reproductions but it also occur during any mitosis (standard cell division) or other phases of the cell cycle.
In short, mutations create genetic variations and differential reproductive abilities between individuals in a population results in a selection (called Natural Selection) for variants that are the best at reproducing.