There is a nice recent book by Richard Kaye, **The mathematics of logic** (Cambridge, 2007).

The book is centered around the completeness theorem, and treats different versions, while developing the required set theoretic and logical background along the way. It begins with a treatment of König's lemma. Then develops a "toy version" of a proof calculus, that introduces the idea of completeness of a proof system. This toy version is designed to require only König's lemma. Additional choice is added to the picture as the proof system grows (so we see Boolean algebras and then propositional calculus, Tychonov's theorem and then first-order logic). Compactness is presented topologically but not in terms of ultraproducts.

Some of the exercises (from the very beginning) are challenging. I found it a very nice introduction to the topic.