How is completeness proved?

Question

How is, for example, Goedel's Completeness theorem, proved if it requires a formula to be true in every model, given that we may not be able to exhaust all possible models?

Answer 1

We only need to show a theory $T$ is consistent iff it has a model: If so, then given a formula $\phi$ that is undecidable in $T$, then $T\cup\{\phi\}$ and $T\cup\{\neg\phi\}$ are both consistent, hence both have models.

Therefore we don't have to exhaust all models, but (find a way to) build only one model from $T$. Henkin's approach can be found in most modern logic books.