OK, we've nailed down earliest publication of the words to Joseph Bever's Christian Songster (United Brethren in Christ, 1858), where it is No. 23 (page 34) under the catchline "Going Over Jordan," first line "I am a pilgrim and a stranger". You can see it at hymnary.org
However, like most songsters, Bever's book does not include music. So when was the tune we know first published with the words?
One poster said the tune is in the 1860 edition of the Sacred Harp, titled Fulfillment. The Wikipedia article on that book gives a table of contents, and I see neither that tune nor "I am a poor wayfaring stranger."
The Wikipedia article on the hymn says it was added to the Sacred Harp in 1935.
So the question remains: when did the words first appear with the tune we use?