Proving that a sentence in first-order logic is not valid
The completeness theorem states, in an equivalent form:


  If a formula $S$ is not valid, then there exists some model $\cal M$ such that $$ {\cal M}\not\models S$$
  or, equivalently
  $${\cal M}\models\neg S $$


This is simply the contraposative of the completeness theorem, as stated on e.g. wikipedia.

This shows that there is always a "certificate of invalidity" as you ask. This is still true if you ask for $\cal M$ to be countable.

However, obviously there is no procedure to compute $\cal M$, by a straightforward argument involving undecidability of Robinson's arithmetic.



Edit: To answer the question of how one might represent such a counter-model:

Unpacking the proof of the completeness theorem shows that such a certificate can be represented by a Herbrand structure, which are the syntactic terms of the language, possibly augmented with constants and function symbols, and recursively enumerable interpretations for the predicate symbols.

In general however, the interpretation of a formula cannot be decided by such a recursive enumeration (but it can be semi-decided).