You can't solve the problem of avoiding gimbal lock in arbitrary rotations, so you rig the game not to ever have arbitrary rotations. You cheat, basically. Gimbal lock is a huge problem in software where free form rotations are allowed, such as 3D modeling packages, CAD, but in games, since we control the world, we can set it up not to have these problems.
Quaternion interpolation works well, but it introduces twist, which is sometimes not what you expect. When you start composing many quaterions, you get some wild rotations, going the long way, or doing an additional 360 twist, and whatnot. Mind you, I'm digging 20 years back in my brain here, I don't remember many specifics anymore.