Can Naive Set Comprehension survive in multi-valued logic? If $\phi$ is a formula in which $x$ is not free, then: 
$(\exists x \ \forall y \ (y \in x \leftrightarrow\ \phi)) $ is an axiom.
This is the inconsistent Naive comprehension axiom.

Is this a paradox limited to classical [binary valued] first order logic?

I mean is this still paradoxical in multi-valued logic. 
The idea is that in multi-valued logic we can have different truth values for $y \in x$, one can in some sense understand the different truth values as difference in probability of membership of $y$ in $x$.
Lets interpret the formula $y \not \in x$ as there is non zero probability of $y$ not being an element of $x$, in other words the probability of $y$ being a member of $x$ is not 1. 
According to this I see the paradox disappear!
The idea is that the asserted set $x$ cannot have probability of $x \in x$ being 1, and also cannot have probability of $x \not \in x$ being 1 for obvious reasons that derives the paradox in binary logic, but it can have intermediate truth value, like for example $0.5$ probability of being in itself (and of course of not being in itself). This way I don't see any problem. 
 A: There has (unsurprisingly) been a decent amount of work on ways to salvage naive set theory by weakening the underlying deductive system - many-valued logic being only one aspect of this. Briefly, the situation is "yes, naive set theory is salvageable, but we have to be careful."

CAVEAT: I'm not an expert on nonclassical logics, so everything below reflects my limited understanding and quite possibly contains serious omissions or errors; however, I hope that it is still useful for giving a taste of the landscape.$^1$


Richard White showed in 1979 that full comprehension is consistent in infinite-valued Lukasiewicz logic; this confirmed a conjecture of Skolem and extended previous work by Skolem, Chang, and Hay (and others). See also Thierry Libert's essay Semantics for naive set theory in many-valued logics, in the volume "The age of alternative logics." But developing this logic is quite nontrivial.
Another interesting paper here is da Costa's On paraconsistent set theory. This lives in the realm of paraconsistent, rather than many-valued, logic, but I think is still relevant to your question. Da Costa establishes the nontriviality of a family of paraconsistent set theories admitting full comprehension (which he introduced in earlier work) relative to the consistency of Quine's NF. This latter question of course is probably the most famous open$^2$ problem in the study of alternative set theories, so in retrospect I don't know how confident we should be in the nontriviality of da Costa's systems. Still, neat!
I'll finally mention Richard Hinton's more recent (= 1994) paper Naive Set Theory with Extensionality in Partial Logic and in Paradoxical Logic, which studies both the many-valued and paraconsistent approaches simultaneously.
There is other work in this context as well, and searching for combinations of the terms (paraconsistent, many-valued, "naive set theory") is fairly fruitful.

On the other hand, it's worth noting that we have to be very careful - there are paradoxes more subtle than Russell's, which even survive naive retreats to paraconsistency. Moh Shaw-Kwei for example presents a version of Curry's paradox, roughly as follows:

Suppose we accept the rule $$p\rightarrow (p\rightarrow q)\implies p\rightarrow q.$$ Fix your favorite sentence $\varphi$ and let $$A=\{x: x\in x\rightarrow \varphi\}.$$ The definition of $A$ tells us that $$(*)\quad A\in A\leftrightarrow (A\in A\rightarrow \varphi);$$ the left-to-right part of $(*)$ and absorption then give us $$(\dagger)\quad A\in A\rightarrow\varphi.$$ But this combines with the right-to-left direction of $(*)$ to give us $$A\in A,$$ which fed into $(\dagger)$ gives us $\varphi$.

So naive comprehension trivializes everything, even without bringing negation into the picture, unless we drop a very mild hypothesis about how implication works. (Actually, Shaw-Kwei proved something somewhat stronger.) Libert's article cited above discusses this and the Lukasiewicz approach.
That is, we cannot conclude that a nonclassical approach to naive comprehension is consistent simply by observing that Russell's paradox doesn't go through.

$^1$A bit of a mixed metaphor, but I like peaty scotch.
$^2$OK fine, Holmes has presented a claimed consistency proof. However, my understanding is that it has not yet been fully vetted.
A: I'm no expert, but it seems to me that naive set theory with ordinary 2-value logic could avoid RP-like internal contradictions if you stick to mathematical theories with some specified underlying set(s) (e.g. the set of natural numbers $N$ in number theory) -- i.e. no arbitrary sets or objects are to be considered after these underlying sets are established.
