Any suggestions for songs that have immortal/reincarnated protagonists? I know about a few already:
The Highwayman/Highwomen
The Braggart’s Song (“I was born about 10,000 years ago…”)
I Ain’t Marching Anymore - Phil Ochs
I Might Have Been Queen - Tina Turner
If you’re counting reincarnation, there’s “Galileo”, by the Indigo Girls.
Actually, come to think of it, almost all religious songs would qualify. Even if you require that the narrator, not just the protagonist, be immortal, there are still lots.
Queen songs from the Highlander soundtrack:
Princes of the Universe
A Kind Of Magic
Who Wants to Live Forever
In the same vein is Handsome Johnny by Richie Havens.
Sympathy for the Devil
Stones
“I can live forever, if I so desire” - The Temptations, I Can’t Get Next To You.
Iron Man
Don’t Fear the Reaper
Four Horsemen
I am, I am, I am Superman; and I can do anything.
Laurie ( Strange Things Happen )- Dickey Lee
*“You’re wrong, son.
You weren’t with my daughter.
How can you be so cruel
To come to me this way?
My Laurie left this world on her birthday -
She died a year ago today.”
A strange force drew me to the graveyard…*
I’ve been alive forever
And I wrote the very first song
I put the words and the melodies together
I am music, and I write the songs…
Ghost Riders in the Sky
Long Black Veil
She walks these hills in a long black veil
She visits my grave when the night winds wail
Nobody knows, nobody sees
Nobody knows but me
Wildfire
She comes down from Yellow Mountain
On a dark, flat land she rides
On a pony she named Wildfire
With a whirlwind by her side
On a cold Nebraska night
*Priests and cannibals, prehistoric animals
Everybody happy as the dead come home
Big black nemesis, parthenogenesis
No one move a muscle as the dead come home.
We feel like Greeks, we feel like Romans
Centaurs and monkeys just cluster round us*
In the night-sky tonight
The witches rise
Wild folk and Lilith’s kind
Lurking, secretly ride the winds.
Monster Mash 
Going back a little farther, Schubert’s The Erlking
*You feel the immortality
It’s you and I until eternity
Chorus:
We live on and on and on, death is weak and we are strong
On and on and on, time is weak and we are strong*
Ghostbusters
Black Sabbath’s NIB.