There are many other solutions. As explained in Douglas Zare's comments, the idea is to choose a cell and to make the step large enough in order to visit it.

Here are the details (which are best followed with pen and paper...). Suppose that at some time, the convex hull of the integers which are already covered is the interval $[a,b]$. We also assume that we are at one end of the interval, say at $b$, and that we are ready to walk with step $s$. We want to visit a given integer $x \in (a,b)$. We want to do this using only cells at the right of $b$, and in such a way that with one more move, we may reach a cell situated at the left of $a$. By induction, it will then be possible to cover $\mathbf{Z}$. I will write $+$ for moving to the right and $-$ for moving to the left.

The proof consists of the following reductions.

We may assume $s > \frac{b-a}{2}$ and $x < \frac{a+b}{2}$. Indeed, starting at $b$ with stepsize $s$, do $++(-+)^{s-1}$. We land at $b+3s$ and are ready to walk with step $3s$. The diameter $L=b-a$ and the step $s$ have changed to $(L+3s,3s)$. Thus the ratio $r=L/s$ has changed to $(L+3s)/(3s) = 1+r/3$. Iterating the process, we can make $r$ arbitrarily close to the fixed point $3/2$, in particular we can make $r<2$ which means $s>L/2$ as requested. It is also clear that iterating the process we can make $(x-a)/L$ arbitrary small, in particular we may assume $x<\frac{a+b}{2}$.

We may assume $b-x \equiv 1 \pmod{3}$. Indeed, we may always achieve this during the first reduction, by doing $++(-+)^{s-2}$ or $++(-+)^{s-3}$ instead of $++(-+)^{s-1}$ (which has the effect to land in $b+3s-1$ or $b+3s-2$ instead of $b+3s$).

Let $b-x=3k+1$ with $k \geq 0$. Do $+(+-)^k -$ and you are at $x$, and then do one more step to the left. This works because by assumption $3k < L < 2s$, so we use only cells at the right of $b$, and because when we are at $x$ we have step $s+2k+2>x-a$ which enables to escape at the left of $a$.

itssize grow relative to the step size. Say, if one would start with a long sequence of +, say n steps; one would be at around n^2/2 eventually I want to go back suppose just with -. Then I'd need still something like (sqrt(2)-1)n steps. Or I need to make order sqrt(x) steps through some area of size x where order sqrt(x) are already forbidden. This seems already rather 'risky'. Of course one has some back and forth option, so this might all work. But in any case the 'margin' with which this might work seems not huge. – user9072 Mar 3 '12 at 2:06