I found the Poe quite interesting, though it seems to me to hover between being a time travel story and a story of reincarnation.

Do you know the Irish story of Nera, which I believe dates from the early Middle Ages? That is remarkably close to being a story of travel into an alternative future - which then, owing to the actions of the protagonist, is prevented from happening. A weird tale, and way earlier than anything else I can think of along these lines. It is not a story of time travel into the past, though.

I liked the passage from Machiavelli.