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