Essentially, all logically valid formulae have proofs in first-order logics.
Remember, logically valid formulae means that if you enumerate all possible interpretations (boolean values for the variables), the formulae remains true.
So you could prove everything that ever exists by creating a set of all possible proofs using the given deduction rules.
This is 1st-order logic so it's a bit more complicated, though you're on the right track (what you stated is the completeness theorem for propositional logic, not first-order logic).
Rather than boolean values for the variables, you need to enumerate all possible...
* Ambient universes where the language is interpreted
* Values (taken from the ambient universe) for the constant symbols
* Sets-of-tuples-of-values (from the ambient universe) for the predicate symbols
* Functions-from-tuples-of-values-to-values (from the ambient universe) for the function symbols
Yup, my definition of interpretation was limited for pedagogical purposes, but I should have been clearer. The propositional logic version is much simpler to understand, but the implications of the theorem are much more interesting in first-order logic, so introducing all of this nomenclature may be too much for someone who isn't motivated yet.
I think going through The Little Schemer by Daniel Friedman and Matthias Felleisen helped me a lot. It builds up your knowledge in a conversational way to achieve understanding of quite complex ideas in simple terms. In that case, it builds up to an understanding of the halting problem, and then to the Y Combinator.
The click felt to me similar to understanding recursion for the first time--it doesn't fit into your head naturally. Once it does "click", even then you have to re-remember it later, and trace your logic on how you "realized" recursion.
Godel's Theorem brings that "feeling" of recursion and takes it to the extreme, in that its subject matter is "meta"-mathematical. So in the same way that recursion can't be grokked in terms of only loops, Godel's Theorem can't be grokked only in terms of equations.
I don't know if that made sense, I've also seen some links in this thread which I think may help as well
Von Neumann said: "In mathematics you don't understand things. You just get used to them."
For practical purpose of getting the completeness theorem to click, my advice would be to stop thinking about it and instead just use it in a bunch of proofs. The way you use it in the a proof is you say something like "...and since, as we've just shown, this sentence phi is true in all structures for the language, it follows that there is a proof P of phi, and therefore..."
If writing such proofs isn't the sort of thing you want to do, then you almost certainly don't actually need to know Goedel's Completeness Theorem, which is a highly technical theorem whose philosophical, epistemological, metaphysical, mystical, and magical applications are all completely overblown by people who want to sell books.
Remember, logically valid formulae means that if you enumerate all possible interpretations (boolean values for the variables), the formulae remains true.
So you could prove everything that ever exists by creating a set of all possible proofs using the given deduction rules.