Correct me if I'm wrong here, but the Parallel Postulate isn't a Gödel statement, because geometry is exempt from Gödel's Incompleteness Theorem (because the axioms of Geometry don't incorporate the axioms for arithmetic on Natural numbers).
It is worthy of keeping in mind, it seems to me, that the essence of the Gödel's Incompleteness Theorem is that "there are some 'truths' about arithmetic of natural numbers we can't prove or disprove using only the axioms for arithmetic of Natural numbers..." The Parallel Postulate isn't a "truth" about arithmetic of Natural Numbers.
It also occurs to me that just because Gödel proved all formal systems that include the axioms of arithmetic of natural numbers will contain undecideable statements, it does not follow that ALL undecideable Mathematical statements are Gödelian in nature, the Euclidean Postulate being one counterexample.