Euler angles (or an equivalent) are implicit in the the way rotation matrices work.

This is not correct (or at any rate is oversimplified). A rotation matrix can represent any arbitrary path through the space of possible rotations (SO(3)) by smoothly varying parameters. There is no inherent “gimbal lock” or the like.

In general I would recommend avoiding Euler angles as a formal representation of rotations. There are several choices of better representations, some of which are described at https://en.wikipedia.org/wiki/Rotation_formalisms_in_three_d...

You're right, I should have said "usually inherent". But it's a major reason for using quaternions.

While you stress the case of gimbal lock occuring within a single rotation, which is typically due to the use of Euler angles, there is also the problem of gimbal lock emerging through the composition of two or more rotations in matrix form. I'm vague on this point but AFAIK this problem can arise with rotation matrices whether or not Euler angles are used. Choose three successive unlucky rotation axes and you've got the problem.

This seems to get so complicated. See e.g. https://en.m.wikipedia.org/wiki/Davenport_chained_rotations