This is not meant to be a complete answer to the question (which I find very interesting), but rather an explanation for why the particular approach you described is bound to run into difficulties. I'm new here, and I'm not sure this belongs as an "answer;" please let me know if this is inappropriate.
It is consistent with ZF that there is a vector space (over the field of two elements) which does not have a basis and yet every nontrivial subspace admits a decomposition into two complementary subspaces. In fact, one such example is quite familiar.
Set $V = \mathcal{P}(\omega)/\mathrm{FIN}$, viewed as a vector space over $\mathbb{Z}/2\mathbb{Z}$ (with, of course, symmetric difference serving as the addition operation). A fairly straightforward Baire category argument shows that $V$ does not have a basis in a model of ZFDC + all sets of reals have the Baire property. However, any subspace $W \subseteq V$ with more than two elements can be decomposed as $S_0 \oplus S_1$: simply fix some element $A \in W$ which does not almost contain every element of $W$ and set
$S_0 = \{B \in W : B \mbox{ is almost contained in A}\}$ and $S_1 = \{B \in W : B \mbox{ is almost disjoint from A}\}$.
I'm sure the same argument actually works for $\mathcal{P}(\omega)$ itself, but I hate thinking about finite sets.
Edit: OK, now I'm worried about offending finite sets. I don't hate thinking about you in general, but I'd rather not think about you in the particular Baire category argument I have in mind.
