The problem is that $V$ is not a set, it is in fact a proper class. A good rule of thumb when it comes to these sort of problems is that if you can map each set into your collection - it's a proper class.
If, on the other hand, you started with a set $A$ (which you already know that it is a set) then you can have the collection of all pairs from the set. The formula which you wrote above is indeed the collection of all singletons and pairs from the set $A$, if you want to exclude the singletons you have to add $x\not= y$ as well.
This is a result from the Subset Axiom/Replacement Axiom - both are schemes and not actual axiom - which state that if you have a formula in one free variable, then the collection of elements which satisfies the formula coming from a set $A$ is a set itself, namely - if it's a subcollection of a set then it is a set.
The replacement axiom is slightly more complicated in that matter, but it says that the range of a function whose domain is a set is also a set, from this the subset axiom can be deduced easily.
Let $X$ be a set, and let $f$ be a function $X \to \mathcal{P}(X)$. To prove Cantor's theorem, we want to show that $f$ is not surjective. (There is no need to assume that $f$ is injective, by the way.)
Your objection is that it is not "logical" to define the set $A=\{x \in X: x \notin f(x)\}$. To the extent that this is a philosophical criticism, it may or may not be correct, but in any case wouldn't amount to showing a "mistake" in the proof. So let's stick to the mathematics.
The formal justification for the existence of $A$ is an instance of the Separation axiom schema: for every set $X$, formula $\varphi$, and parameter $p$ there is a set denoted $\{x \in X: \varphi(p,x)\}$ whose elements are the elements $x$ of $X$ such that $\varphi(p,x)$ holds.
Your objection seems to be that this definition of $A$ leads to a contradiction if $X$ is the "set of all sets" and $f$ is the identity function. This is a good and important observation. If the conjunction of two things leads to a contradiction, then (at least) one of them must be wrong. Either Cantor's argument is wrong, or there is no "set of all sets."
After having made this observation, to ensure that one has a consistent theory of sets one must either (1) disallow some step in Cantor's proof (e.g. the use of the Separation axiom) or (2) reject the notion of "set of all sets" as unjustified. Mainstream mathematics has done (2), for the reason that you (and Russell) pointed out. It is also possible to do (1) instead, as in New Foundations set theory.
EDIT: I missed some things on my first reading. Your third-to-last paragraph, if all its claims were true, would show that set theory as used by Cantor was inconsistent. Note that this would be quite different (mathematically, if not philosophically) from showing that there was a mistake in his proof! A proof of inconsistency would be a perfectly valid proof, not to mention an important one. In any case, some of your claims are not true, as I explain below.
Letting $f$ be the identity function, you argue that $A$ must be empty:
Now look at the definition of $A$: there is no element of $X$, such that $x \notin f(x)$...
This step is not right. There are plenty of possibilities for $x$ such that $x \notin x$. Perhaps you are confusing $x \notin x$ with $x \ne x$.
Then you argue that $A$ cannot be empty.
...in fact $A$ can not be even an empty set: because even for empty set: $f(\emptyset)=\emptyset$, thus $\emptyset \notin A$.
This step is not right either. First, as Greg Martin points out, $\emptyset \notin \emptyset$, so if $\emptyset \in X$ then $\emptyset \in A$. Second, even if $\emptyset \notin A$ it doesn't follow that $A \ne \emptyset$. Perhaps you are confusing "$\in$" with "$=$" again.
Best Answer
Yes, your proof is correct.
You can actually rephrase your proof and make it constructive. Doing so only slightly modified the proof. Instead of doing case analysis on whether $X \in X$, we can phrase this step of the proof as follows:
Suppose $X \in X$. In that case, we would have $X \notin X$, which is a contradiction. Therefore, we must have $X \notin X$.
Now we have $X \notin X$. We also trivially have $X \in V$. Therefore, $X \in X$. This is a contradiction. Therefore, there must not be any such set $V$. $\square$