Yes, the group of automorphisms of $\ell^\infty(\mathbb{Z})$ preserving the $W^*$-algebra structure is the group of permutations of $\mathbb{Z}$.
On the one hand, any permutation of $\mathbb{Z}$ acts as an automorphism of $\ell^\infty(\mathbb{Z})$.
On the other hand, any $W^*$-algebra automorphism of $\ell^\infty(\mathbb{Z})$ sends characters - that is, homomorphisms $\chi: \ell^\infty(\mathbb{Z}) \to \mathbb{C}$ - to characters, so it defines a permutation of the characters. By the Gelfand-Naimark correspondence, there is a compact Hausdorff space $\beta\mathbb{Z}$ called the Stone-Cech compactification of $\mathbb{Z}$ such that
$$\ell^\infty(\mathbb{Z}) \cong C(\beta\mathbb{Z}) $$
Points of $\beta\mathbb{Z}$ are the same as characters $\chi: \ell^\infty(\mathbb{Z}) \to \mathbb{C}$. Every point $n \in \mathbb{Z}$ defines a character $\chi$ by
$$ \chi(f) = f(n) $$
Not all characters are of this form, as pointed out by Yemon Choi and Uri Bader. However, the weak-$\ast$-continuous characters are. If $\alpha$ is a $W^*$-algebra automorphism of $\ell^\infty(\mathbb{Z})$ and $\chi$ is a weak-$\ast$-continuous character, $\chi \circ \alpha$ is again weak-$\ast$-continuous. So, every $W^*$-algebra automorphism of $\ell^\infty(\mathbb{Z})$ defines a permutation of the integers.
The concept of 'weak-$\ast$-continuous character' is a bit fancy, so I like Nik Weaver's simpler argument below. Just as the integers give the weak-$\ast$-continuous characters on $\ell^\infty(\mathbb{Z})$, they give the isolated points in $\beta\mathbb{Z}$ - but this is easier to understand, and easier to prove. By the functorality of the Gelfand-Naimark correspondence any automorphism of $\ell^\infty(\mathbb{Z})$ comes from a homeomorphism of $\beta\mathbb{Z}$, and these clearly map isolated points to isolated points. So, any automorphism of $\ell^\infty(\mathbb{Z})$ gives a permutation of the integers.