This rotation behavior occurs because the first rotation causes a rotation in the axes as well. This would require you to recalculate the axis to use for the second rotation. Unfortunately this problem isn't the result of gimbal lock and won't go away if you're switching to quaternions.
A quick and dirty solution would be to change the order of your rotations depending on whether the cube is rolling in the x or y direction. I don't know if it's possible to change the rotation order for one node, but if you multiply the rotation matrices you end up with the same result. If you're sticking to nodes, use two Matrix Math and a Matrix Mix node. I just decided to switch to a script to reduce the amount of wiring.
This approach would require you to keep track of the cube's direction and manually add keyframes for the script input which changes the matrix multiplication order.
The fact that the orientation of the cube might change whenever you switch could lead to problems if you replace the cube with an object with less symmetry. But then it might be better to search for another approach as the x and y position of an empty alone isn't sufficient to determine the desired orientation of the final object.