Shuffling a list while keeping order relative to related elements
Your problem can be phrased as generating a random linear extension of a partial order. The partial order in your phrase is generated by your constraints. There is a classical algorithm of Matthews described in his paper Generating a random linear extension of a partial order. This might even be implemented in some library.

Your particular case is generating a random lattice word of certain content (for the reduction, delete all letters or all numbers). This is a concept occurring in representation theory of the symmetric groups, generalizing the classical ballot sequences. If you're lucky you might find an algorithm for generating a random lattice word (in Mupad, for example, somebody implemented an algorithm for generating all lattice words).