An orientation in 4D can be represented by a pair of quaternions. If you want to rotate (change your orientation) you would multiply one pair of quaternions (representing your current orientation) by another pair of quaternions (representing the rotation) componentwise, yielding a new orientation.
This will not gimbal lock.
Regarding using 4x4 matrices: This will result in unintended shears and stretches due to rounding errors. Renormalising the matrices will be complicated and expensive. Also, interpolation will be more complicated and expensive.