"Euler Angles" you can think of as a function $(S^1)^3 \to SO_3$ or $\mathbb R^3 \to SO_3$. The derivative of this function does not always have rank 3, so you have degenerate submanifolds where the function is many-to-one. In this special case that's called "gimbal lock".
One formalism that avoids this is quaternions. You can of course use other formalisms, and many other formalisms are naturally related to the quaternion version, so people tend to gravitate to the quaternion version. One version that's closely related to quaternions would be to use the exponential map for the unit quaternion group. But this also has "gymbal lock" but of a different kind. But it does have the rather appealing interpretation as rotations about arbitrary axis -- this is perhaps more useful if you're only interested in rotations that differ from the identity matrix (or some given matrix) by a small amount, they're very natural coordinates on "small scales" in $SO_3$.
Are there any special properties you'd like for coordinates on $SO_3$? That might give a sense for where you want to go with this.
Edit in response to 1st comment: There's various conventions for Euler angles. Let's use what Wikipedia calls "Proper Euler Angles" http://en.wikipedia.org/wiki/Euler_angles
Given a unit vector $\vec v \in \mathbb R^3$ and a number $\theta \in \mathbb R$, let $R_{\vec v, \theta}$ be the rotation matrix which fixes $\vec v$ and which rotates counter-clockwise by an angle $\theta$ in the plane orthogonal to $\vec v$. One version of "Proper Euler angles" would be:
$$R_{(1,0,0), \theta_1} R_{(0,1,0), \theta_2} R_{(1,0,0), \theta_3}$$
The "Tait-Bryan" variant would use the three distinct vectors, notice above we only used the standard vectors for the xy-plane. The Tait-Bryan variant is the one appropriate to pitch/roll/yaw of an aeroplane. Wikipedia has an excellent picture:
In this case you'd have
$$R_{(1,0,0),\theta_1} R_{(0,1,0), \theta_2} R_{(0,0,1),\theta_3} $$
$\theta_3$ would be the roll, $\theta_2$ the pitch and $\theta_1$ the yaw. To relate my coordinates to the picture, $(1,0,0)$ is the direction the plane is pointing. $(0,1,0)$ is the direction of the left wing. $(0,0,1)$ is the direction of the yellow axis sticking out of the top of the plane.
You can write out the matrices quite explicitly:
$$ R_{(1,0,0), \theta} =
\pmatrix{ 1 & 0 & 0 \cr
0 & \cos \theta & -\sin \theta \cr
0 & \sin \theta & \cos \theta }$$
So in this case, one occurance of "gimbal lock" is $\theta_2 = 0$. In the Tait-Bryan variant it would be when the aeroplane is either pointing straight up or down, which is $\theta_2 = \pm \pi/2$.
Actually Wikipedia is right. Of course you have to keep the axis-to-angle relation. If rotating with angle $\theta$ around the $z$-axis, you cannot suddenly use this angle to rotate around the $x$-axis. So it is true that an $XYZ$ moving-axis representation with angles $(\alpha,\beta,\gamma)$ (resulting in $R=R_x(\alpha)R_y(\beta)R_z(\gamma))$ is equivalent to a ZYX fixed-axis rotation with angles $(\gamma,\beta,\alpha)$ (again resulting in $R=R_x(\alpha)R_y(\beta)R_z(\gamma))$ and therefore the same rotation.
But I wouldn't think Shoemake to make such a dumb error and neither his code to be incorrect. But since I don't have any insight into this code or this book chapter, I would rather say that this paragraph is just poorly worded (like many statements about Euler angles suffer from notational inconsistencies).
Or you have just restated it incorrectly. Look at the quotation, no matter what transformations he means with XEDR and XEDS, his formulas still match his statements, since $R=R_z(\alpha)R_y(\beta)R_x(\gamma)$ is indeed the same as $R=R_z(\gamma)R_y(\beta)R_x(\alpha)$ with just $\alpha$ and $\gamma$ swapped. So with only seeing this quotation, he is perfectly right with his statements.
Best Answer
I don' find the sentence you quoted from wikipedia so much illuminating... It's saying that Euler angles want to decompose a rotation as a product of three rotations $RPY$. It is obvious that every rotation applies to the frame of the previous one. This is exactly the good thing about Euler angles... the bad thing is that if you have a rotation which varies with continuity, the three rotations $R,P,Y$ are not guaranteed to vary continuously.
My suggestion is to think about the real gimbal lock, which might happen to a compass in a plane. Notice that the compass in a plane gives you exactly the Yaw angle. Suppose that the plane is heading north and makes a loop. When the plane passes the vertical the yaw angle passes abruptly from north to south and might cause the compass to lock in an incorrect position.