If I had to build something like this in 1000 BC, I'd use a cart with wheels that did not turn at all and put a heavy statue on top. Then, whenever it came time to change direction, I'd get a few guys to hoist the statue up, while someone else rotated the cart independently. (And there are easily mechanical ways to make this process simpler.) You could recalibrate using the sun or stars.
A differential gear would automate all of this, but would be unmaintainable, expensive, would barely work for more than a few hundred yards, and all this in an era where labor is slave-cheap.
EDIT:
Another way would be to use multiple carts, only move one at a time, and calibrate it from the others, survey style. Cumulative error should be far smaller this way, and you would have fewer terrain problems.