Cyclic vectors for the shift operator

This is part of what the theory of Hardy spaces is for. There is a complete characterization of the cyclic vectors for the shift, though it applies to the Fourier transform of $x$ rather than the sequence $x=(x_0, x_1, \dots)$ itself. (For convenience I am starting the indexing at 0 rather than 1.) As in Fedor's answer, we can view the $x$ sequence as the sequence of Fourier coefficients of an $L^2$ function $h$ on the unit circle, which can be extended analytically to the disk $|z|<1$ by $$ h(z) = \sum_{n=0}^\infty x_n z^n. $$ The function $h$ is said to belong to the Hardy space $H^2$, which sits as a closed subspace of $L^2$ on the circle. In this model, the right shift becomes the map $h(z)\to zh(z)$. It is then a fact that $\log|h|$ belongs to $L^1$ of the unit circle, and the inequality \begin{equation} \log|h(0)|\leq \frac{1}{2\pi} \int_0^{2\pi} \log|h(e^{i\theta})| \,d\theta\end{equation} always holds. Such an $h$ is called an outer function if equality holds (so in particular $x_0=h(0)\neq 0$ is necessary but not sufficient). Finally, it is a theorem that $h$ is cyclic for the shift if and only if $h$ is outer. All of these facts may be found e.g. in the book Banach Spaces of Analytic Functions by Kenneth Hoffman.

Not always. Let $(e_n)$ be the standard basis of $l^2$ and take $x = e_1 - 2e_2$. For any $k$ the vector $S^kx$ is orthogonal to the sequence $(2^{-n})$, so $x$ is not cyclic.

You ask for a handy criterion that $\overline{\rm span}(x, Sx, S^2x, \ldots)$ equals $l^2$. I don't know, but note that this subspace is invariant for $S$, so it is necessary and sufficient that it contain the vector $e_1$. So a sufficient condition for cyclicity is that the series mentioned by András in the comments should converge. I guess that is probably pretty close to a necessary condition, too, because you need to use a series close to this one in order to get close to $e_1$.

I suppose my conjecture is that $x$ is cyclic if and only if András's series converges weakly. You can see that weak convergence might be necessary by taking $x = e_1 - e_2$. This vector is cyclic because anything that is orthogonal to $S^kx$ for all $k$ must be a constant sequence and hence, if it is in $l^2$, the zero sequence. But the series you get by trying to solve $\sum a_k S^kx = e_1$ is $x + Sx + S^2 x + \cdots$, which only converges weakly.

Consider $x=(x_0,x_1,\dots)\in \ell^2$ as a function $F_x:=\sum_{k=0}^{\infty} x_k z^k\in L^2({\mathbb S}^1)$ (this is norm-preserving). Then shift operator multiples functions by $z$. If $x$ is so that $F_x(a)=0$ for some complex $a$, $|a|<1$, then also $a^k F_x(a)=F_{S^k x}(a)=0$, and since $$ f(z)\rightarrow f(a)=\frac1{2\pi i}\int \frac{f(z)dz}{z-a} $$ is a continuous functional on $L^2$ restricted to our space (well, not just our, but Hardy space), we see that orbit of $x$ under $S$ lies in a proper closed subspace. In Nik Weaver's example function is $1-2z$ and $a=1/2$.