Another great mediaeval story: Farid ud-Din Attar's "Conference of the Birds", written around 1200. It has some odd parallels to "Sweeney", though it's a Sufi parable rather than a Christian one.

The Icelandic sagas are great stuff too. "Njal's Saga" has the world's first courtroom drama and "Grettir the Strong" is probably the last literary expression of paganism.