I believe none of these interpretations so far are completely correct, although they point in the right direction. The key is "but." It has TWO meanings here, both of which are relevant: but ="if not" (conditional)" and also but = "without the circumstance that, without also". If I am right, then
There's ne'er a villain dwelling in all Denmark
But he's an arrant knave.
means both
There is not a villain in all of Denmark
If he (Claudius) is not a rascal.
and also
There is not a villain in all of Denmark
that is not a rascal.
Those two interpretations parallel these two examples of 'but' in the dictionary.com link above:
Nothing would do (=be satisfactory) but that I should come in.
= Nothing would be satisfactory if I should not (~= cannot manage to) come in.
It never rains but it pours. = Whenever it rains, it always seems to pour (rain heavily) !
Basically, the verses you quoted are a likely case of dramatic irony. From wikipedia: "This type of irony is the device of giving the spectator an item of information that at least one of the characters in the narrative is unaware of (at least consciously), thus placing the spectator a step ahead of at least one of the characters." (< Wikipedia.)
This is dramatic irony because Hamlet is starting to make indirect innuendo about the immorality of the King and his actions, without mentioning the King himself. That innuendo will become more and more direct as the play progresses, culminating in the Murder of Gonzago spectacle, at which point Hamlet's accusations become obvious. By contrast, at this early point in the play, even if Hamlet's friends appear to have no idea what Hamlet is really talking about, Hamlet is aiming at something deep, since he just swore his friends to secrecy. That is something he would not do if he was merely making the observation that there's a lot of villainy in Denmark.