Suppose I have the set of all things $\{a, b, c,... \}$. It seems to me that $ \mathcal P \{a, b, c,... \} $ would be the set of all sets, which sounds like it includes the set of all sets that do not contain themselves. However, I can't envision deriving that set from the power set of $\{a, b, c,... \}$.
My thinking is that, so long as there are no sets in $\{a, b, c,... \}$, then the paradox doesn't arise. Otherwise, my reasoning, or my knowledge, is shamefully off.
Where did I go wrong?
On
If sets can only contain things and are not allowed to contain sets, then your reasoning is ok and you escape the paradox. But then you have the trouble of defining what things are, and what happens when you want to talk about multiple sets of things at the same time? Given these hardships, it makes sense to concede that sets may contain sets. What then?
Considering your set $A$, is $\{\{a,b\},\{c\}\}$ in the powerset of $A$? It isn't, and yet it is a set. (Try proving this with the axioms!) Notice that it is in the powerset of the powerset of $A$, however. Perhaps then we could describe sets as objects that are inside some amount of repetitions of the powerset operation!
Unfortunately, $\{\{a,b\}, c \}$ is not in the powerset of $A$, nor the powerset of the powerset of $A$, or any repetition of this concept. This is an unfortunate consequence of allowing things to be in sets. In order to construct $\{\{a,b\},c\}$, we need to apply other constructions like pairing and comprehension. This adds a lot of extra complication to the task of describing every set, and is completely unnecessary.
Finally, if we only allow sets to be in sets, then we can describe the collection of all sets with only the powerset and union operations. This is because (unlike things) the empty set has the nice property of being a subset of every set. From here we can see the motivation behind the construction of the Von Neumann universe which does in fact generate every possible set (while not being a set itself).
On
If you allow arbitrary subsets, you can prove that the set of all things cannot exist.
Proof: Suppose this universal set $U$ exists such that $\forall x: x\in U$.
Then there must exist a subset $S$ of $U$ such that $\forall x:[x\in S \iff x\in U \land x\notin x]$.
Clearly, $S\in U$. Then, using only the rules of logic, we can obtain the contradiction $S\in S \iff S\notin S$.
So, the set $U$ cannot exist.
Corollary: Every set excludes something.
The power set axiom presents no problems.
It's not clear at all what you mean by "thing". Is the number $4$ a thing? What about the ordered pair $(5, 2)$? Or $\mathbb N$? Some of those may seem to you to be more or less like "things" than others, but in modern mathematics they are all regarded as sets. It sounds like you want to craft a variation of set theory that has both a rigidly-enforced distinction between "things" and "sets of things", and such a theory can be crafted -- see http://en.wikipedia.org/wiki/Urelement. The "things" in such a theory are often called "atomic elements" or "atoms", for natural reasons.
But in fact it turns out that "things" are entirely unnecessary. We can do just fine without them! In standard set theory we begin with the empty set $\varnothing$, start creating power sets, and are able to build up everything we need for mathematics. Ironically, though, in a theory that has no "things" in it, the "set of all things" is the empty set!
As for Russell's Paradox, it arises as soon as you start talking about "the set of all sets." If there were a set of all sets, then you would consider the subset of all sets that do not contain themselves, and that leads to a paradox. So in any version of set theory, whether there are atomic elements or not, there is no set of all sets.