I don't know about non-stabilizing, but rigidity provides many examples that stabilize quickly.

1) Let π be the fundamental group of a finite volume hyperbolic manifold M of dimension ≥ 3 with no symmetries (that is, no nontrivial self-isometries). Negative curvature implies that π is centerless, so the map π -> Aut(π) is injective. Mostow-Prasad rigidity says that Out(π) = Isom(M), so the lack of isometries implies that Out(π) is trivial and Aut(π) = π. [This works verbatim for lattices in higher-rank semi-simple Lie groups subject to appropriate conditions.]

2) Let π=F_{d} be a free group of rank 2≤d<∞. Then Aut(F_n) is a much larger group; however, Dyer-Formanek showed that 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 π=π_{1}(S_{g}) is the fundamental group of a surface of genus g≥2, then Aut(π) is the so-called "punctured mapping class group" Mod_{g,*}, which is much bigger than π. Ivanov proved that Out(Mod_{g,*}) is trivial, and since Mod_{g,*} is again centerless, we have Aut(Aut(π_{1}(S_{g}))) = Aut(π_{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 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 = π_{1}(M) as in the first example and G = Isom(H^{n}) [which is roughly 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_{∞} unsatisfying because even though 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;Z/2Z) = Z/2Z. (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 x Z/2Z -> G x Z/2Z, the composition

G -> G x Z/2Z -> G x Z/2Z -> G

is an isomorphism. From this we see that Aut(G x Z/2Z) / G = H^{1}(G;Z/2Z) = Z/2Z. By examination the extension is trivial, and thus Aut(G x Z/2Z) = G x Z/2Z. However, the image Inn(G x Z/2Z) is the proper subgroup G.

Comments: looking back, this feels very close to your original example of R x Z/2Z. 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;Z/2Z) having larger dimension, say H^{1}(G;Z/2Z) = (Z/2Z)^{2}, this blows up quickly. You get Aut(G x Z/2Z) = G x (Z/2Z)^{2}, but then Aut(Aut(G x Z/2Z)) is the semidirect product of H^{1}(G;Z/2Z^{2}) = (Z/2Z)^{4} with Aut(G) x Aut(Z/2Z^{2}) = G x 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 x (Z/2Z)^{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.