> The sun and stars are completely useless for determining longitude without a clock.

This is not completely true. The stars (and planets) provide for a very nice clock when viewed with sufficient resolution.