Call a partition of $2^\mathbb{N} = A\cup B$ a parity partition if, for any $n\in\mathbb{N}$, flipping the $n$th bit of any element of $A$ results in an element of $B$, and vice-versa.
Given a choice function for the equivalence classes in $2^\mathbb{N} / E_0$ (where $x E_0 y$ if $x$ and $y$ agree on a tail) we can easily construct a parity partition; just let $x\in A$ if $x$ differs from the representative of its equivalence class by an even number of bits.
But we can do even better; given a nonprincipal ultrafilter $U$ over $\mathbb{N}$, define $$ x\in A \iff E(x) = \{n\;:\; x\upharpoonright (n+1) \mbox{ has an even number of ones}\}\in U $$ Then, if $x\in 2^\mathbb{N}$ and $y$ is the same as $x$ but with the $n$th bit flipped, we have $$ E(y)\cap [n,\infty) = (\mathbb{N}\setminus E(x))\cap [n,\infty) $$ so if $x$ were in $A$, we would have $E(x)\in U$, hence $E(y)\not\in U$, hence $y\in B$.
Question: Assume there is a parity partition. Is there a nonprincipal ultrafilter over $\mathbb{N}$?
Remarks: (1) Obviously, this question only makes sense when working over ZF + some restriction of choice, like DC.
(2) One can show that the parts of a parity partition are neither Lebesgue measurable nor have the Baire property, so at least some choice is involved.
(3) There is an inverse to the function $E$ defined above, namely $ F : 2^\mathbb{N} \to 2^\mathbb{N} $ defined by $F(x)(0) = 1 - x(0)$ and $F(x)(n+1) = (x(n) + x(n+1)) \pmod{2}$ (after the usual identification of $2^\mathbb{N}$ and $\mathcal{P}(\mathbb{N})$.)
(4) Here's the beginning of an attempt; suppose $2^\mathbb{N} = A\cup B$ is a parity partition, and without loss of generality say the sequence of all zeroes is in $A$. Put $U = \{E(x)\;:\; x\in A\}$. There are a couple properties of $U$ that we can prove;
(i) Notice that $E(x)$ is finite if and only if $x$ has a finite and odd number of $1$'s. Since the sequence of all zeroes is in $A$, it follows that such an $x$ must be in $B$, or in other words; $U$ only contains infinite sets.
(ii) Suppose a set $S$ is not in $U$. Let $x = F(S)$; then we must have $x\in B$. Let $y$ be the same as $x$, with the $0$th bit flipped; then $y\in A$ and $E(y) = \mathbb{N}\setminus E(x) = \mathbb{N}\setminus S$. Hence $U$ is "ultra".
However, it's not clear to me that $U$ is closed under finite intersections or taking supersets.
It seems that the answer was staring me in the face all along; since you can get a parity partition from either a nonprincipal ultrafilter or an $E_0$-selector, and the existence of just one of these objects does not imply the existence of the other (see this very interesting MO question), it follows that you can't get an ultrafilter or an $E_0$-selector just from a parity partition.