$\DeclareMathOperator{\Aut}{Aut}$I don't know about non-stabilizing, but rigidity provides many examples that stabilize quickly.
1) Let $\pi$; be the fundamental group of a finite volume hyperbolic manifold $M$ of dimension $\ge 3$ with no symmetries (that is, no nontrivial self-isometries). Negative curvature implies that $\pi$; is centerless, so the map $\pi\to \Aut(\pi)$ is injective. Mostow-Prasad rigidity says that $\operatorname{Out}(\pi) = \operatorname{Isom}(M)$, so the lack of isometries implies that $\operatorname{Out}(\pi)$ is trivial and $\Aut(\pi) = \pi$. [This works verbatim for lattices in higher-rank semi-simple Lie groups subject to appropriate conditions.]
2) Let $\pi=F_d$ be a free group of rank $2\le d\lt \infty$. Then $\Aut(F_n)$ is a much larger group; however, Dyer-Formanek showed that $\operatorname{Out}(\Aut(F_n))$ is trivial. Thus since $\Aut(F_n)$ is clearly centerless, we have $\Aut(\Aut(F_n)) = \Aut(F_n)$.
3) Interpolating between these two examples, if $\pi=\pi_1(S_g)$ is the fundamental group of a surface of genus $g\ge 2$, then $\Aut(\pi)$ is the so-called "punctured mapping class group" $\text{Mod}_{g,^*}$, which is much bigger than $\pi$. Ivanov proved that $\operatorname{Out}(\text{Mod}_{g,^*})$ is trivial, and since $\text{Mod}_{g,^*}$ is again centerless, we have $\Aut(\Aut(\pi_1(S_g))) = \Aut(\pi_1(S_g))$.
In each of these cases, rigidity in fact gives stronger statements: Let $H$ and $H'$ be finite index subgroups of $G = \Aut(F_n)$ or $\text{Mod}_{g,^*}$. (This class of groups can be widened enormously, these are just some examples.) Then any isomorphism from $H$ to $H'$ comes from conjugation by an element of $G$, by Farb-Handel and Ivanov respectively. In particular, $\Aut(H)$ is the normalizer of $H$ in $G$. Rigidity gives the same conclusion for $H = \pi_1(M)$ as in the first example and $G = \operatorname{Isom}(H^n)$ [which is roughly $\operatorname{SO}(n,1)$]. It seems that by carefully controlling the normalizers, you could use this to construct examples that stabilize only after $n$ steps, for arbitrary large $n$.
Edit: I find the examples of $D_8$ and $D_\infty$ unsatisfying because even though $\operatorname{Inn}(D)$ is a proper subgroup of $\Aut(D)$, we still have $\Aut(D)$ isomorphic to $D$. Here is a general recipe for building similarly liminal examples. Let $G$ be an infinite group with no $2$-torsion so that $\Aut(G) = G$ and $H^1(G;\Bbb{Z}/2\Bbb{Z}) = \Bbb{Z}/2\Bbb{Z}$. (Edited: For example, by rigidity, any hyperbolic knot complement with no isometries has these properties; by Thurston, most knot complements are hyperbolic.) The condition on the $2$-torsion implies that for any automorphism $G \times \Bbb{Z}/2\Bbb{Z} \to G \times \Bbb{Z}/2\Bbb{Z}$, the composition
$$G \to G \times \Bbb{Z}/2\Bbb{Z} \to G \times \Bbb{Z}/2\Bbb{Z} \to G$$
is an isomorphism. From this we see that $\Aut(G \times \Bbb{Z}/2\Bbb{Z}) / G = H^1(G;\Bbb{Z}/2\Bbb{Z}) = \Bbb{Z}/2\Bbb{Z}$. By examination the extension is trivial, and thus $\Aut(G \times \Bbb{Z}/2\Bbb{Z}) = G \times \Bbb{Z}/2\Bbb{Z}$. However, the image $\operatorname{Inn}(G \times \Bbb{Z}/2\Bbb{Z})$ is the proper subgroup $G$.
Comments: looking back, this feels very close to your original example of $\Bbb R \times \Bbb Z/2\Bbb Z$. Interesting that it's (seemingly) much harder to find group-theoretic conditions to force the behavior the way you want, while topologically it's easy.
Also, if you instead take $G$ with $H^1(G;\Bbb Z/2\Bbb Z)$ having larger dimension, say $H^1(G;\Bbb Z/2\Bbb Z) = (\Bbb Z/2\Bbb Z)^2$, this blows up quickly. You get $\Aut(G \times \Bbb Z/2 \Bbb Z) = G \times (\Bbb Z/2\Bbb Z)^2$, but then $\Aut(\Aut(G \times \Bbb Z/2\Bbb Z))$ is the semidirect product of $H^1(G;(\Bbb Z/2\Bbb Z)^2) = (\Bbb Z/2\Bbb Z)^4$ with $\Aut(G) \times \Aut((\Bbb Z/2\Bbb Z)^2) = G \times \operatorname{GL}(2,2)$. Already the next step seems very hard to figure out. However, if you had enough control over the finite quotients of $G$, perhaps you could show that the linear parts of these groups don't get "entangled" with the rest, so that the automorphism groups would act like a product of $G \times (\Bbb Z/2\Bbb Z)^n$ with something else, with n going to infinity. If so, this could yield an example where the isomorphism types of the groups never stabilize.