Would non-euclidean geometry be possible if Euclid's 5th theorem can be proved using the 4 postulates Elliptic/Hyperbolic geometry maintain the first 4 postulates while modifying the 5th postulate in some way. Now if the 5th postulate of Euclidean geometry was provable from the other 4, wouldn't that mean that that non-euclidean geometry is impossible since they have as axioms the first 4 postulates? 
Could this be a proof that 5th postulate of Euclidean geometry cannot be proved using the first 4 and hence must be taken as an axiom (Godel's Incompleteness Theorem, is that you?)
 A: This assertion of yours is true:

Now if the 5th postulate of Euclidean geometry was provable from the
  other four, wouldn't that mean that that non-euclidean geometry is
  impossible since they have as axioms the first 4 postulates?

But it's not hard to prove that the 5th postulate can't be proved from the other four since there are models of both elliptic and hyperbolic geometry in Euclidean geometry - for example, the Poincare disk model. That means any contradiction in non-Euclidean geometry must already be present in the first four axioms. (Whether or not those four are self contradictory is another question entirely.)
A: Elliptic geometry also requires a modification of other axioms, not just the 5th.  So, in your sense, it is impossible.  
"In order to achieve a consistent system, however, the basic axioms of neutral geometry must be partially modified."
Elliptic Geometry at Wolfram MathWorld
Isn't your question rather like asking what would happen if we could prove that $1 = 0$?  
A: Non-Euclidean geometries are possible--and arose--because Euclid's fifth postulate seems unprovable but not self-evident. No one has been able to prove it, and the fact that so many have tried seems to argue that it is not self-evident. Hence Lobachevski developed his geometry "in the uncertainty" whether Euclid's fifth postulate is true, and offered a theory of parallels that does not rest on it.
