First order logic is undecidable, so there is (as you note) no mechanical method for determining first order validity. So what's the next best to a mechanical method for trying to establish (in)validity?
The trouble with looking for natural deduction proofs is that the introduction rules allow you to deduce more and more complex wffs, and thus don't stop you spinning off down blind alleys (even when there is a proof to be discovered).
Better, then, to use a method without introduction rules, where as you grow a proof the length of wffs at least doesn't grow and ideally decreases. Two options spring to mind. One is downward-branching tableau proofs [as in Richard Jeffrey's lovely Formal Logic: Its Scope and Limits, or my Jeffrey-for-Dummies, officially titled An Introduction to Formal Logic]. The other option is certain sequent systems.
The tableau system in particular is very student-friendly, and with a bit of practice, on "nice" examples you'll usually find a closed tableau if there is one to be found, and find an open tableau and be able to read off a valuation which falsifies the wff being tested if the wff is invalid. This is perhaps your best buy!
For example, let's use a tableau to test $(\forall x P(x) \rightarrow \forall x Q(x)) \rightarrow \forall x (P(x) \rightarrow Q(x))$. We start by assuming that's false (i.e. its negation is true), which comes to assuming
$$\forall x P(x) \rightarrow \forall x Q(x)$$
$$\neg\forall x (P(x) \rightarrow Q(x))$$
The latter is equivalent to
$$\exists x\neg (P(x) \rightarrow Q(x))$$
So, if that's true there must be an object in the domain which satisfies the condition, which we can dub $a$, so
$$\neg (P(a) \rightarrow Q(a))$$
whence
$$P(a)$$
$$\neg Q(a)$$
Now look at the first line. We have to consider cases. We have either the negated antecedent or the consequent:
$$\neg\forall x(Px)\quad\quad|\quad\quad \forall xQ(x)$$
On the right hand branch we immediately have a contradiction, however, because we can instantiate the universal $\forall xQ(x)$ with $a$ to get $Q(a)$.
So look at the left branch. We can continue that
$$\exists x\neg P(x)\quad\quad\quad\quad\quad\quad$$
$$\neg P(b)\quad\quad\quad\quad\quad\quad$$
where we have to use a new name to dub the witness for the existential. And now we are stymied. So the assumption that the original wff is false doesn't lead to contradiction. So it can't be valid.
In fact, we can read off the open branch of the tableau the interpretation with just two elements in the domain -- call them $a$ and $b$ -- where $P(a)$, $\neg P(b)$, $\neg Q(a)$ and it doesn't matter for $Q(b)$. And that interpretation will falsify the test formula! [For a more careful exploration of this kind of thing, if it is unfamiliar to you, see my book.]
Hint
To show that the formula is not valid, you have to find an interpretation such that the complex formula is False.
Being a disjunction, this means that the sought interpretation must falsifies every disjunct.
We can try with a simple interpretation $\mathcal I$ with domain $I = \{ 0,1,2,3 \}$.
Try with $P^{\mathcal I} = \{ (0,0), (0,1), (0,2), (1,0), (1,2), (1,3) \}$ as interpretation of the predicate symbol $P$.
(A) We have that $(0,0) \in P^{\mathcal I}$ and thus it is not true that $\lnot P(a,a)$ for every $a$.
(C) We have that $(0,1) \in P^{\mathcal I}$ and also $(1,0) \in P^{\mathcal I}$; thus it is not true that $P(a,b) \to \lnot P(b,a)$ for every $a,b$.
(B') We have that $(0,1) \in P^{\mathcal I}$ and $(1,2) \in P^{\mathcal I}$ and also $(0,2) \in P^{\mathcal I}$. Thus, it is not true that $(P(a,b) ∧ P(b,c)) \to ¬P(a,c)$, for every $a,b,c$.
In the same way, you can check (B).
Best Answer
Your approach is correct. Suppose that $\forall xP(x) \vee \forall xQ(x)$ is true and $\forall x(P(x) \vee Q(x))$ is false. Negating the quantifier and applying De Morgan's law gives $\exists x(\neg P(x) \wedge \neg Q(x))$, so that $P(a)$ and $Q(a)$ are false for some $a$ in the domain. However, two applications of universal instantiation imply that either $P(a)$ or $Q(a)$ are true. This is a contradiction, since $P(a)$ and $Q(a)$ are false.
An easy way to check check formulas of propositional and predicate logic for validity is the method of semantic tableaux, which gives a proof procedure for predicate (and other more exotic) logics.