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.)

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.
