0-1 law argument not presuming measurability? Is there a version of the 0-1-law that applies as well to non-measurable sets? (I.e., a proof that doesn't presume the set under consideration to be measurable.)
 A: Usually, one defines a tail event as an element of $\bigcap_{n=1}^\infty \left\langle \{X_m: m\ge n\}\right\rangle $ where $\langle\dots\rangle $ means the $\sigma$-algebra generated by the listed random variables. There is no question of measurability then. Perhaps a tail event can be defined differently. The OP proposed the following concrete version (for symmetric Bernoulli variables):  

does there exist a non-measurable subset $S \subset   [0,1]$ such that for every natural $k$: if $|x - y| = 1/2^k$, then $x \in S$ iff $y \in S$? 

No. If $S$ is not Lebesgue null, then it contains a measurable set of positive measure, say $A$. By the Lebesgue density theorem, $A$ has a point of density, say $x_0$. For any $\epsilon>0$ there is a dyadic interval $I$  (say of length $2^{-m}$) such that $x_0\in I$ and $|A\cap I|>(1-\epsilon)2^{-m}$. Let $B\in [0,1]$ be the union of translates of $A\cap I$ by multiples of $2^{-m}$. By assumption $B\subset S$. Since $|B|>1-\epsilon$, and $\epsilon$ was arbitrary, it follows that $[0,1]\setminus S$ is a null set.
A: The question in the post is difficult to decipher and has no obvious relation to the question in the comment, which is:

Does there exist a non-measurable subset $S \subset   [0,1]$ such that for every natural $k$: if $|x - y| = 1/2^k$, then $x \in S$ iff $y \in S$? 

The answer to this question, assuming choice, is yes. 
Start from the equivalence relation $\sim$ on $\mathbb R$, which says that $x\sim y\iff x-y\in\mathbb Q$, and choose exactly one real number in each equivalence class of $\sim$. The resulting set is $S_0$. Consider $S_1$ the union of the translates $S_0+2^{-k}\mathbb Z$ over every positive integer $k$ and let $S=S_1\cap[0,1]$. Then $S$ satisfies the defining property above, except that it remains to show that $S$ is not measurable.
The argument is similar to the one used to show that $S_0$ is not measurable. Let $Q_0=\{\pm2^{-k}\mid k\geqslant1\}$ and $Q=(\mathbb Q\cap[-1,1])\setminus Q_0$, then, for every $q\ne0$ in $Q$, $S\cap(S+q)=\varnothing$. The union of the sets $S+q$ over every $q$ in $Q$ contains $[0,1]$ and is contained in $[-1,2]$. Thus, if $S$ is measurable with measure $s$, each $S+q$ is also measurable with measure $s$, and
$$
1\leqslant\sum_{q\in Q}s\leqslant3,
$$
which has no solution since $Q$ is countably infinite.
