At first I understood definition of ruler and compass as operations not in space, but instead operations on the surface of the sphere. So these would spherical tools, not spatial, which is a good starting point.
Using spherical circles, you can construct the perpendicular bisector of the segments $AA'$ and $BB'$, just as you would in the plane, by intersecting circles of equal radius around the endpoints. This bisector is a greatcircle which is the locus of all points at equal distance from $A$ and $A'$ resp. $B$ and $B'$. Note that this great circle will intersect the great circle through $A$ and $A'$ in two points, so there are two antipodal “midpoints” to the segment, not only one. But since we are interested in the bisector itself, we don't have to worry about midpoints.
Now that you have these two bisectors, look at their intersections. They as well will intersect in two antipodal points, which are the points where your axis of rotation intersects the sphere. And the angle of rotation is the angler under which these bisectors intersect.
So what if your ruler and compass really operate in space? Drawing great circles through two given points, the ruler operation on the sphere, would become a compass operation in space, drawing a circle around the center of the sphere through the two given points.
The easiest way to construct the perpendicular bisectors would involve intersecting three spheres: the sphere on which the four points live and two spheres of equal radius around $A$ and $A'$. But your definition does not involve a tool for this.
But at this point I feel like an extension of your toolbox would be required in any case. Your definition of a compass operation is too tight. For example, it doesn't even cater for the case of drawing two circles of equal radius. Furthermore, one often wants to draw circles around a given point but with arbitrary radius; with your definition that would be impossible because I'd already have to know to points on the preimeter of the circle, i.e. two points equal distance away from the center. One possible generalization here would be a circle with a given center, a given point on the perimeter and a line through the center which the circle will intersect. Conceptually you'd construct a sphere around the center through the given perimeter point, and where that sphere intersects the line would be your second perimeter point for the circle operation as you specified it.
Extended spatial compass
So for now I'll assume that there are two distinct compass operations. In both cases you give the center and a line through that center which the circle has to intersect. In the first case you also give a point on the perimeter, whereas in the second case you give the radius (taken as a distance between two other points) and a second line the circle will intersect as well. So in both cases you fix the center, the plane and the radius, without overspecification.
Using these tools, you can work out the plane of the perpendicular bisector of $A$ and $A'$, and then draw that bisector.
- Connect $A$ and $A'$ with a line $a$
- Draw a circle around center $A$ through line $a$ and an arbitrary point $P$ in space, not on $a$ and at a distance form $A$ which is more than half the distance $AA'$
- Draw a circle around $A'$ with radius $AP$ through lines $a$ and $AP$
- Both circles are in the plane $AA'P$, and have sufficiently large radii, so they will intersect in two points $Q_1$ and $Q_2$
- Construct a circle around the center $O$ of the sphere, passing through both lines $OQ_1$ and $OQ_2$ and with the radius of the sphere, i.e. $OA$
- Perform steps $1$ through $5$ for $B,B'$ instead of $A,A'$
This way you can construct the perpendicular bisectors with tools very similar to what you originally asked for.