The point here is that you can usually get rid of evaluating transcendental functions in the middle of the number crunching part of your code, which is where you would care most about saving operations.
I don't think there's a way to do rotations without transcendental functions (or square roots) that isn't equivalent to merely precomputing the transcendental functions or square roots.
Maybe square roots are faster, in which case you have a point that avoiding transcendental functions is the way to go.
Yes, there's a sqrt. (And another for gravity.) No trig needed or wanted.
I am recommending using the Cartesian (x, y) coordinate representation instead. This is often called a “complex number” x + iy on the “complex unit circle”, or you can think of it as (cosine, sine) if you prefer. Composition of rotations in this representation is still straight-forward: (a + ib)(c + id) = (ac – bd) + i(ad + bc).
If you need to compress this down to one number for transmission or storage, you can take the stereographic projection (“half-angle tangent”), (x, y) ↦ y / (x + 1), and optionally also reduce the precision. This saves you at least half the bits vs. storing the pair of coordinates, and is relatively inexpensive to compute (takes one division per point).
You are right that to normalize an arbitrary vector requires taking a square root. Fortunately, this doesn’t need to be done too often.
As an added bonus, this method generalizes much more easily than angle measure to representing higher-dimensional rotations and points on higher-dimensional spheres. For instance, I recommend using cartesian coordinates (or the stereographic projection for compression) instead of latitude and longitude for storing points on the 2-sphere such as geographical places. Many pieces of mapping software are constantly converting back and forth (implicitly or explicitly) between latitude/longitude vs. cartesian coordinates for computing distances, directions, and areas, finding intermediate points, applying 3-dimensional rotations, clipping shapes, and so on. This is slow and complicated vs. just using Cartesian coordinates as the internal representation.
It is usually unnecessary to compute the angle measure corresponding to a rotation unless communicating with a human. Angle measure is just one of several possible representations, and it’s only the most common because it gets taught to every child.