We find then that for any set A, there is a set B which is not in A. How does this - that everything contains something outside it - entail that 'nothing contains everything',
Suppose there were a set $U$ that we thought did contain absolutely everything. But we showed, as you said, that for any set $A$, there is a set $B_A$ which is not in $A$. We can apply this construction to $U$ and obtain a set $B_U$ that is not in $U$. But then $U$ does not contain everything, since it does not contain $B_U$.
Halmos's claim that there is no "universe of discourse in set theory" is a little too strong; it depends on what kind of set theory one chooses. The claim is true, however, for ZF set theory, which is the set theory most commonly used in foundational mathematics.
Does this come as a result of the unrestricted application of the axiom of specification, or in spite of it?
I'm not sure here what you're asking. Truly unrestricted comprehension is logically incoherent, as the Russell paradox shows, because unrestricted comprehension says that for any property $\phi$ there is some set $S_\phi$ that consists of precisely the objects for which $\phi$ is true. But the Russell paradox shows that this is simply false; there are properties for which there is no such set, the simplest such being the property of not belonging to oneself. If $\rho(x)$ is the property $x\notin x$, then there simply is no set of $S_\rho$ of all $x$ for which $\rho$ holds.
Since in mathematics we usually try to avoid choosing axioms that are false, the unrestricted comprehension axiom won't do, and we make do instead with one of several restricted form of set comprehension.