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 theorem, 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.

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.

Yes, the group of automorphisms of $\ell^\infty(\mathbb{Z})$ preserving the $W^*$-algebra structure is the group of permutations of $\mathbb{Z}$.

It's pretty easy to see this. 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 (homomorphisms to $\mathbb{C}$) to characters, so it defines a permutation of the characters. But the characters of $\ell^\infty(\mathbb{Z})$ are all of the form $f \mapsto f(n)$ for some integer $n$. (This follows from the Gelfand-Naimark theorem and a little work.) So, any $W^*$-algebra automorphism of $\ell^\infty(\mathbb{Z})$ comes from a permutation of the integers.

We could say $C^*$-algebra instead of $W^*$-algebra in the last paragraph and everything would still be true.

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 theorem, 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.