Gimbal Lock is a problem in the brain, not in the math. It's very common :-)
Every possible composite orientation is representable in Euler angles. Every possible composite orientation is also representable using quaternions. Every possible composite orientation is also representable using axis-angle. All three representations are equivalent.
When Gimbal Lock gets you into trouble is when you try to decompose a single orientation into separate components, and then construct it using “forward reasoning.” Because the original coordinate system changes in each step, you can't assume that some reference point that existed in the original coordinate system, is the same, or is even non-degenerate, in the new coordinate system.
One work-around for this is “Tate-Bryant” Euler Angles, where the rotations are expressed in terms of the new coordinate system. E g, “rotate down” then “rotate around up” would rotate around the new up which in your case is the same as the old forward. This is closer to “airplane” controls – when you're going straight down, and then crank on the rudder, the “forward” still turns rightwards from the new point of view.
Another alternative is to sequence the rotations in a way that they mostly make sense to your brain. For heading/pitch/roll, you will want to apply roll first, then pitch, then heading. Important here is to make sure that the pitch represents the final amount of pitch you want – if you want to go slightly out the right, you can't pitch down 90 degrees; you pitch down however much is the total pitch of the final orientation you want.
Another little-known geometry secret: There's no thing as a “right handed” or “left handed” rotation. A 90 degree positive rotation of the X vector around the Z vector always ends up yielding the Y vector. “left handed” and “right handed” only show up once you start to physically interpret your math. You need to use the same convention when going from physics to math, as you use when going back out from math to physics, but the math itself does not change based on handedness, only interpretation does.
Welcome to 3D graphics :-)
