Depending on if you want to have true 360-degree freedom, you could implement a system where each object has an up vector, a right vector and a forward vector. When rotation occurs, those three vectors rotate along with the object. Whenever an object rotates, you then use one of those three axis to rotate the object around, using the arbitrary rotation axis matrix:
https://en.wikipedia.org/wiki/Rotation_matrix#Rotation_matrix_from_axis_and_angle
Example code (axis is the axis of rotation and radians is the degrees to rotate):
axis = vector_normalize(axis);
float ct = cosf(radians);
float st = sinf(radians);
float ci = 1 - ct;
float x = axis.x, y = axis.y, z = axis.z;
return matrix_make(ct + x * x * ci, y * x * ci + z * st, z * x * ci - y * st, 0,
x * y * ci - z * st, ct + y * y * ci, z * y * ci + x * st, 0,
x * z * ci + y * st, y * z * ci - x * st, ct + z * z * ci, 0,
0, 0, 0, 1);
As an example, when an object pitches up, rotate the object along the right axis and also rotate the "orientation" vectors along that same axis. When you perform another rotation (for example, turning right), rotate the object around the new up vector for the specified number of degrees (and, also rotate the orientation vectors).
Another option is to use quaternions.