Nitpick: The North Star (Polaris) wasn't used over 4000 years ago:
So now you can see why Polaris will not always be aligned with the north spin axis of the Earth - because that axis is slowly changing the direction in which it points (precession)! Right now, the Earth's rotation axis happens to be pointing almost exactly at Polaris. But in the year 3000 B.C., the North Star was a star called Thuban (also known as Alpha Draconis), and in about 13,000 years from now the precession of the rotation axis will mean that the bright star Vega will be the North Star.
Well, good point, but every moment in history had its fixed south and north stars, you could find easily, if you were familiar with the sky. Which everyone was back then. As well as some animals, who also use the stars for navigation.
There’s no good reason to assume that in the absence of an extremely bright star that happens to be north-aligned that a culture navigated the stars with a north-anchored reference ;)
The reason would be, that you can see that the sky is rotating around a certain point in the north, or south depending where you are. All the stars are changing - but this point is not. So even when there is no bright star at that spot - there will be star constellations around pointing towards it. A fixed point or area of reference ( and with no artificial lights, there definitely would be some star to see).
But of course if you really know the dark sky well, there are a lot more points of references, you will remember what constellations will be where at what time of the night at what season. Or where the moon is, etc.
