(A) The "Barber paradox" is not really a paradox, properly so called.
What we have here is a perfectly good proof by reductio that there can't exist someone in the village who shaves all and only those in the village who don't shave themselves. For suppose there is such a person, $B$. Then, by hypothesis, for all $y$, $B$ shaves $y$ if and only if $y$ doesn't shave $y$, where the variable $y$ runs over people in the village. So, in particular $B$ shaves $B$ if and only if $B$ doesn't shave $B$ -- contradiction!
Now, we have no antecedent reason to suppose there might be a barber who shaves all and only those who don't shave themselves. Hence it should be no particular surprise to learn that as a matter of simple logic that there can't be one.
And it is indeed a matter of simple logic. Generalizing, take any binary relation $R$ defined over the domain $U$ of widgets. Then this is a straightforward theorem of first-order logic: $$\neg\exists x\forall y(Rxy \leftrightarrow \neg Ryy)$$ with the quantifiers running over the domain $U$. Hence, whatever relation $R$ you take, there can't be a widget which is $R$-related to all and only those widgets which are not $R$-related to themselves. (Exercise, prove that formal wff in your favourite system of first-order logic!)
So far, there is nothing paradoxical going on. We can only speak really of a paradox or antinomy when a (seemingly) compelling proof clashes with other (seemingly) compelling ideas. And that isn't yet the case here.
(B) Suppose though -- to make the famous historical connection -- that we are thinking not about the shaving relation but about set-membership. Then we have this particular instance of our first-order theorem: $$\neg\exists x\forall y(x \in y \leftrightarrow y \notin y)$$ with the quantifier running over all sets. Hence there is no set containing all and only the normal sets (where a set is normal if and only if it doesn't contain itself.
But now note that unlike the Barber case, this result does clash with some assumptions that we might rather naturally have had about sets. For suppose we start off wedded to the ideas that (i) we can collect together all the $X$s into a set of $X$s, whatever $X$s might me -- so in particular, there is a super-collection $U$ that collects together all the sets (so $U$ is a set of all the sets), and (ii) for any given set $X$ and property $P$, there will be a subset of it containing just those members of $X$ with property $P$, and (iii) there is a perfectly good property of being a normal set, i.e. one which doesn't have itself as a member.
Then (i), (ii) and (iii) commit us to the existence of a set $Russell$, the subset of the super-collection $U$ which contains all and only the normal sets -- so $Russell$ is the set of all sets which are not members of themselves.
But as we've seen the $Russell$ set can't exist because of our simple logical theorem. Which shows that we can't hold (i), (ii) and (iii) together. And this traditionally is called a paradox -- though it is, strictly speaking, only paradoxical to the extent to which we previously might have been firmly wedded to (i), (ii) and (iii).
Unless I'm missing something, this isn't possible unless the theory in question, which I'll call "$T$," is inconsistent: taking $\psi=\varphi$ we would have $$T\vdash (\varphi(\ulcorner\varphi\urcorner)\leftrightarrow\neg\varphi(\ulcorner\varphi\urcorner)).$$
That is, there is a sentence $\alpha$ (namely, $\alpha\equiv\varphi(\ulcorner\varphi\urcorner)$) such that $T\vdash (\alpha\leftrightarrow\neg\alpha)$. This clearly means that $T$ is inconsistent.
In a bit more detail, to make it clear that all rules are being followed, your assumption is that for each $\psi$ we have $$T\vdash (\varphi(\ulcorner\psi\urcorner)\leftrightarrow\neg\psi(\ulcorner\psi\urcorner)).$$ So taking $\psi$ to be $\varphi$ yields as a specific instance the contradiction-inducing sequent above; there's no need to pass to a "meta-equivalence."
Re: the role of diagonalization as a general framework for such arguments, see e.g. A universal approach to self-referential paradoxes, incompleteness and fixed points. My brief spiel on the matter would be that Lawvere's fixed point theorem has many such results as instances, but in no way "trivializes" them - you still need to set up the category in question and check its relevant properties. But there is definitely something real there.
Best Answer
Here is a preliminary version of a paper by Noson Yanofsky on paradox and self-reference that may be of interest. There is also a final version in the Bulletin Of Symbolic Logic.