Groups with all subgroups normal

These are called Dedekind groups, and the non-abelian ones are called Hamiltonian groups. The finite ones were classified by Dedekind, and the classification extended to all groups by Baer. The non-abelian ones are a direct product of the quaternion group of order 8, an elementary abelian 2 group, and a periodic abelian group of odd order (or all of whose elements have odd order).

Periodic abelian groups all of whose elements have odd order can be quite complicated, but the finite ones are direct products of cyclic groups.

Your example does not have the property that all of its subgroups are normal when n ≥ 4. The subgroup generated by x1*x2*x3 is not normal, since (x1*x2*x3)^x4 = (ax1)(ax2)(ax3) = ax1*x2*x3, but x1*x2*x3 has order 2. For n = 3, your group is Q8 x 2, and so is Hamiltonian.

The cyclic group of order 6 and the direct product Q8 x 3 are two groups of non-(prime power) order with every subgroup normal.

The keyword is "Hamiltonian group". There is a classification of them, modulo the classification of abelian periodic groups (that is, torsion groups) with elements of odd order. You'll find the details, due to Dedekind and Baer, in W. R. Scott's Group Theory, for example.

Yes, these are called Hamiltonian groups.