On the uniqueness given the data $\{\epsilon_{2^n}\}_{n\ge1}$. As observed by Terry Tao in a comment, the sign in $xa_{m-1}\pm a_{m-2}$ is forced precisely when for some $r$, one has $$[x^r](xa_{m-1})=[x^r]a_{m-2}=1\mod 2$$ (because for integers $a,b$ in $\{-1,0,1\}$ the equation $|a+\epsilon b|\le1$ has a unique solution $\epsilon$ in $\{-1,1\}$ if and only if $|a|=|b|=1$). But the parity of the coefficients of the $a_m$ is known, for $a_m=\sum_{0\le j\le{n/2}}{m-j\choose j}x^{m-2j}\mod 2$ (this follows immediately by induction from the additive formula of binomials).

Therefore, the value of $\epsilon_m$ is free if and only if $ {m-i\choose i-2}{m-i\choose i-1}$ is even for all $i\ge2$. But this is never the case if $m$ is not a power of $2$: indeed, if for some $a$ one has $2^a<m<2^{a+1}$, then $2\le i:=m-2^a+1\le 2^a$, so $m-i=2^a-1$, and both $ {m-i\choose i-2}$ and ${m-i\choose i-1}$ are odd, because all binomials ${2^a-1 \choose k}$ for $k=0,\dots,2^a-1$ are odd.

On the uniqueness given the data $\{\epsilon_{2^n}\}_{n\ge1}$. As observed by Terry Tao in a comment, the sign in $xa_{m-1}\pm a_{m-2}$ is forced precisely when for some $r$, one has $$[x^r](xa_{m-1})=[x^r]a_{m-2}=1\mod 2$$ (because for integers $a,b$ in $\{-1,0,1\}$ the equation $|a+\epsilon b|\le1$ has a unique solution $\epsilon$ in $\{-1,1\}$ if and only if $|a|=|b|=1$). But the parity of the coefficients of the $a_m$ is known, for $a_m=\sum_{0\le j\le{n/2}}{m-j\choose j}x^{m-2j}\mod 2$ (this follows immediately by induction from the additive formula of binomials).

Therefore, the value of $\epsilon_m$ is free if and only if $ {m-i\choose i-2}{m-i\choose i-1}$ is even for all $i\ge2$. But this is never the case if $m$ is not a power of $2$: indeed, if for some $a$ one has $2^a<m<2^{a+1}$, then $2\le i:=m-2^a+1\le 2^a$, so $m-i=2^a-1$, and both $ {m-i\choose i-2}$ and ${m-i\choose i-1}$ are odd, because all binomial coefficients ${2^a-1 \choose k}$ for $k=0,\dots,2^a-1$ are odd.