1. Easy. Program a computer with the axioms of ZFC. Not powerful enough? Program it with ZFC+Con(ZFC). Repeat as necessary.
2. The Turing machine itself is logically consistent. The semantic interpretation of its data need not be logically consistent: it's possible to write a computer program that prints "2+2=5" to the screen. Likewise, a human brain may be made of physics and physics may be logically consistent, but the semantics of the data in the brain (the "beliefs") need not be consistent.
3. No, no need to reject collapse itself (though I'm more of an Everett guy). Penrose postulates the existence of a new level of physics that is not Quantum Mechanics. People who aren't careful call it an extension of QM, but QM's computing model is limited to solving a small subset of NP problems (BQP) in polynomial time, and BQP is theorized to be a proper superset of P. However, Penrose's proposed physics would allow solving problems outside of NP in polynomial time. Hence, Penrose's physics IS NOT quantum physics.
4. It is physically impossible for computers (as we understand them today) to solve problems outside of the set we call "Turing complete". Penrose claims that there's at least one problem outside that set that the human brain can nonetheless solve: checking the consistency of formal systems. If Penrose's assumption were true, computers (as we understand them today) would consequently be strictly less powerful than the human brain. The crux of Penrose's position is accepting this consequence as true, then asking how that's possible. I reject that hypercomputation of problems beyond Turing-completeness is what's happening, i.e. that humans simply hold unjustified beliefs about the answers to such problems.
I do not doubt that Penrose is an intelligent and educated person. However, his expertise is General Relativity. It's bad enough when he tries dipping his toes into Quantum Physics, but when he wades into Physics of Computation, he is no longer acting as an expert, but as an interested layman. It's only because of the authority he holds as a GR expert that his argument is treated seriously, but that authority is not actually relevant to his argument.