Liland, I've had occasion to sing religious songs socially with some Primitive Baptists who use word only books. I can still remember a stint with people from several churches who went through 4 or 5 tunes for the same set of words. I've also heard them sing Amazing Grace to several different tunes.

"While Shepherds Watched thier flocks" is a great example of a text that's been used with innumerable tunes. The tune for "On Ilkly Moore" was written for "Grace 'tis a Chaming Sound," was popularly adopted for use with Shepherds & finally "On Ilkla Moor Bah T'at" was written to go with the tune. Here's a thread on it. This sort of existing words/tune/other existing words/new words for tune evolution is not uncommon with hymns of any sort. The words/tune at the same time seems to have really caught steam in the mid to late 19th century.

"Hark the Herald" by Charles Wesley, like his non-Christmas hymns, was set down with no particular hymn tune in mind. Cookham is a really good tune, like most of the other triple time tunes in Sacred Harp, it dances. According to the '91 ed. it's earliest publication was 1760 in a book called Harmonia Sacra.

Your best bet to find what other tunes were used before the current ones is to just go through old hymnals. There's no sure way to know which were really popular but the more different places you find the pairing in, the more popular it was. I also look at denominational hymnals as more likely to have been really used than some others.

I seem to recall seeing Amazing Grace set to Arlington in either a Moravian or Methodist Hymnal. Sacred Harp singers use it for alternate verses to Hallelujah & almost any other common meter tunes that have only 1 verse in the book.

Since you've got a Sacred Harp, see Plenary for other words for the 'Auld Lang Syne' tune. Portuguese Hymn is a different translation of Adetes Fideles, but I don't really like the arrangement.

The meter indexes in hymnals will help you find other tunes for 'How firm' (or any other hymn) that could work for words, but there's no real way to know what's really been used. I'm sure Cyberhymnal has a meter index. Here's the Sacred Harp.