Also from LotR, we have various other ainur and fey (all of the wizards, Sauron, the Balrog, Shelob and her momma Ungoliant, etc.). And then there’s Tom Bombadil, about whom nobody knows very much, but even Galadriel (who’s over twenty thousand years old) refers to as “Eldest”.
In Asimov’s later novels, we learn that R. Daneel Olivaw has persisted as a sort of guardian of humanity for many millenia But he has the advantage of being a robot.
Speaking of guardians of humanity, we could include any of the Protectors from Niven’s Known Space, or the Arisians from Doc Smith’s Lensman books.
Also from Known Space we have Lucas Launcelot Garner, who isn’t actually immortal and doesn’t have anything in particular going for him, but who just happens to be born at the right time to catch the wave of advances in gerontology, and keeps on living just long enough to take advantage of the next life-extending breakthrough. Later characters in Known Space, of course, are born with those breakthroughs already in place, but Garner’s case seems more noteworthy.
If we’re including folklore, there’s the Wandering Jew, who scorned Jesus on the way to the Crucifiction, and is now cursed to walk the world until Judgement Day.
In Feist’s Riftwar books, there’s the great wizard Macros the Black, who’s been a major mover and shaker on many worlds, and turns out to be (it’s implied) the son of the afore-mentioned Wandering Jew, who shares his curse.
The Incarnations in Piers Anthony’s Incarnations of Immortality have a very limited sort of immortality: Each of them can “die”, but each only in his or her own manner.
