I'll describe the idea I have for a straightedge-only construction. We are working in the projective plane for simplicity. You are allowed to
- Connect two points with a line.
- Find the intersection of two lines.
- Mark an arbitrary point lying on/not lying on some already constructed lines.
A construction's result should be independent of arbitrary points. Imagine as if they're supplied by an "evil goblin" and you want your result to be independent of his malice.
Let $f$ be any collineation of the projective plane. Then if your arbitrary points in a certain were $A_1, A_2, \dots A_n$ and the resulting point/line of the construction was $B$ then the "evil goblin" could have given you the arbitrary points $f(A_1), f(A_2), \dots f(A_n)$ and these result would have been $f(B)$.
Therefore you can only construct projective invariants of the initially given points. You cannot, then, halve an interval, as that is not a projective invariant of the two endpoints. This is because collineations act 3-transitively on a line.
Having three points with given distances on a line (one may be at infinity, this is equivalent to the ability to construct parallel lines) is enough for the projective invariance to go away. We can use this construction: http://en.wikipedia.org/wiki/File:Pappusharmonic.svg to get the harmonic conjugate point on the line and from there we can construct any rational distance. With duality this extends to angles, resulting in right angles, so we pretty much regain Euclidean geometry.
This is considered folklore among Hungarian students, mostly thanks to Lajos Pósa.