If you really want to use just straight-edge and compass, don't go into $3$-space at all! Coxeter points out the equivalence between the inversive plane and hyperbolic space in the paper The inversive plane and hyperbolic space. In this particular situation one can think of *lines* as pairs of points in the inversive plane. Two pairs of points correspond to perpendicular lines of hyperbolic space when the two pairs are harmonic. So the problem is:

Given two pairs of points $(a,b)$ and $(c,d),$ to construct using straightedge and compass the (unique) pair $(x,y)$ harmonic to both.

Fenchel asserts the existence of such a thing, and relates them to square roots, but without mentioning the geometric argument, so here goes.

We first start off easy, and assume that $a = \infty.$ We define the (two) *geometric means of $(c,d)$ with respect to b* to be given as follows. (Basically they are the complex square roots of $d$ where $b = 0$ and $c = 1$.) Bisect the angle $\angle c b d$ by a line $\ell.$ Let $C_c, C_d$ be the circles centered at $b$ through $c,d$ respectively. Intersect these with $\ell$ to get four points $p_c, p_c', p_d, p_d',$ so that $(p_c,p_d)$ separate $(p_c',p_d').$ Let $q$ be the midpoint of $p_c$ and $p_d.$ Draw the circle $D$ centered at $q$ through $p_c$ and $p_d.$ Draw the perpendicular $\ell_\perp$ to $\ell$ at $b,$ and intersect it with $D$ at a point $r$. Then draw the circle $E$ centered at $b$ through $r$, and intersect it with $\ell$ at the points $s_{(c,d)},t_{(c,d)}$. These are the geometric means of $(c,d)$ with respect to $b$.

Now, it should be that $(s_{(c,d)}, t_{(c,d)})$ is harmonic to both $(\infty, b)$ and $(c,d).$ (I haven't worked this out yet.) So that's what we were looking for. In the case that $a \neq \infty,$ just let $C$ be the circle centered at $a$ through $b,$ and denote by $I_C$ the inversion in $C.$ Then the points we're looking for are $I_C(s_{I_C(c,d)}, t_{I_C(c,d)}) = (\sigma_{(c,d)}, \tau_{(c,d)}).$ These give the endpoints for the common perpendicular to the hyperbolic lines with endpoints $(a,b)$ and $(c,d).$

It's probably all in Fenchel, anyway....