Since a quaternion can encode any orientation, you can actually let it define both the position of an object moving around a sphere, and its direction.
I made a tiny demo once with a bunch of guys walking around a sphere, and my code to update them looks like this:
(math should be possible to simplify further, and the math library is our in-house one, but this is hopefully easy to read, to show the principle:)
//Turn, yaxis of quat is up-vector of object
Vec3 yaxis = minion->pos.yaxis();
minion->pos *= Quat(yaxis,turnSpeed*dt);
//Then move forward, xaxis of quat is the right vector of object
Vec3 xaxis = minion->pos.xaxis();
minion->pos *= Quat(xaxis,walkSpeed*dt);
pos is a quaternion, and both turnSpeed and walkSpeed is in radians/s
The Quat constructors create a new quaternion with a rotation around the specified axis, that I then rotate the pos quaternion with.
Then when building the matrix for drawing them, I just first translate with Vec3(0,sphereRadius,0) (rasing the model up along y-axis in model space) before applying the quat.
You could also pre-translate all your models vertices, and then just apply the quat.
This way, all you need to store in your object i a single quat (plus the two speed floats to make it move), no need for position, direction vector, nor rotation.
If you need the position in world space of your object, you can take the y-axis of the quat and scale it with the radius.
The z-axis is your direction vector.
Distance along the sphere between two objects can be calculated from the smallest angle between the two quats defining the pos/rotation of the two objects.