The classical proof You have mentioned shows how powerful logic may be. The crucial point of a proof is the use of the law of excluded middle (A or not(A)). In that case we are lucky to have knowledge of which of the two possibilities: 

i) $\sqrt{2}^{\sqrt{2}}$ is rational or 
ii) $\sqrt{2}^{\sqrt{2}}$ is not rational 

takes place to be. But You can imagine a statement A about natural numbers such that neither A nor not(A) is provable (in, say, ZFC). Now we may use analogously the particular statement of the law of excluded middle "A or not(A)"  in some proof of some statement B. In that case the statement B is proved both by supposing A and by supposing not(A) and at the same time we know in advance that we shall not resolve which of the cases has the place to be. In such a proof the purely logical priciple of excluded middle becomes even more important (or at least as important) than the axioms of actual mathematical structure (in this case that of natural numbers). It is this power that made some mathematicians (e. g. intuitionists under the head of Brouwer) to think that logical principles such as that of exluded middle have caused the paradoxes discovered in the beginning of the XX century.
For a classical mathematician the proof of B would be a legitimate proof since he/she believes that either A or not(A) is valid for natural numbers even if we shall never prove neither of them. (This position is often called platonism because it presupposes the "independent existence" of natural numbers.) Intuitionist, however, says that it is a hypothesis and to turn this reasoning into a valid proof one should prove that indeed one of those possiblities has the place to be.