Edit: Would of course not be a spoofing attack.
I think the military can go even further and verify that the GPS data is correct.
Charts, sextant, and regular visual observations are all strictly necessary.
Some kind of semaphore would probably be handy too.
Of course the SR-71 probably never had cloud cover problems. :)
edit: I think this one: https://www.youtube.com/watch?v=tj9UwKQKE3A
No. You need an actual clock and charts. The sun and stars are completely useless for determining longitude without a clock.
The Moon on the other hand is marginally useful because its phases can be looked up. But its resolution is poor.
This is not completely true. The stars (and planets) provide for a very nice clock when viewed with sufficient resolution.