Avandonk,
Unfortunately you just quoted or intreptred Godel's Incompleteness theory to the guy who topped maths at Uni in 1983.
That's not at all what Godel stated, rather he said in simplitistic terms once a system (say a logic system or a mathematical system) gets beyond a certain level of complexity (that is he implied once a system is powerful enough to be actually real-world useful), then its loses the power to be fully deterministic. So once you move a logic system above a certain level of grunt it inherits infinite possibility for asking questions that must have a clear answer but can't be answered by the rules of that system. I.e. our reality - is there a god? In maths Godel showed using an Godel Universal Truth Machine you could ask a question which itself had an embedded but reversed GUTM that flips the correct answer and then when you point the first GUTM at the inverted second GUTM and ask it what happens you have a contradiction - the orignal GUTM can't prove or disprove the second inverted GUTM because both are fully state aware and both will therefore conflict in any answer given.
http://www.miskatonic.org/godel.html
So in essence once a system achieves a certain level of power - it looses precision in its ability to have assured outcomes. So a ruler can always measure an inch, but a PC can't always get the right answer to the problems it attempts to solve. Simple things work, but they can only do Mickey Mouse tasks. Powerful things mostly work, but there is a level of power or capability beyond which things are always guaranteed to have some level of failure! Enhancing such a powerful system with more rules, or inference systems, or logic, or capabilities or more levels of redundancy doesn't address the problem, it only brings in new and more subtle points of failure!
So bottom line your quote "Or to paraphrase him 'a finite system always has paradoxes and non proveable truths' ... In other words the Universe has to be 'very big to infinite or even better bigger than infinite' so there are no internal inconsistencies." doesn't quite hit the mark. A finite system above a certain level of complexity always has areas it can never resolve or illuminate. A universe is not proven to need size nor complexity to avoid internal inconsistencies; I wish that it were that simple!
* * *
My personal belief is science doesn't preclude nor prove a directed intelligence rather than blind luck created our Universe; rather it can predict and go some ways to explore the mechanisms used for creation and why things are the way they are. It can show what likely happened when the big red creation button was pushed, but not if a God or a stray quantum possibility tripped this switch.
But equally faith is often reinforced for various reasons by folk who wish to intreptret reality and recorded past events in a certain way. In this faith must contend with science and what can be observed and validated to be internally consistent and what can't. As said above 2 + 2 must always equal 4, even for very large values of 2! Once you get into trickier proofs you can either show a system with a known level of consistency and tens of millions of validation points works; or you can try and twist out an outcome you wish and either say its unknown or scientists have it all wrong (a.k.a. bad science or psuedo-science).
On th esubject of is there a God - its neither proveable or dis-proveable to science by a long, long shot. As I said before its kinda like as relevant as gnats arguing about nuclear fusion; the capabilities and/or very existence of an infinite supreme being not of our existence are beyond us to predict, test or verify in any material way, shape or form. Regardless of human longing for a God, gods or no gods, it doesn't change the underlying reality or result. God or gods either exist or they don't. You can not use logic to either confirm or deny your point of view in any material way - it has to be a faith call; science can't solve this one either way for anyone.
At best science can say if a powerful, directed intelligence (or random chance) initiated creation as a set and forget event - what likely mechanisms were used so as to be self sustaining and internally consistent with the self propgating reality or laws of that system as it came into existence.