Hi, Liz. What your source terms a "free melody" is a characterisic of Irish sean nos ("old style") singing. The habit of rhythmic "interpretation" most likely exists in many more folk traditions as well. Specifically to your question of accompaniment for such a song, the only criterion is that the singer(s) and accompanist(s) need to be in agreement on what they're doing. The mark of a good accompanist is his/her ability and willingness to follow the vocalist. The mark of an instrumental clod is his/her insistance on playing like a fokking metronome, irrespective of what the singer(s) is/are doing. Anyone so rigid as to say that "Shenendoah" should not be done with instrumental accompaniment is a clod of the other sort. Such people miss out on much beautiful music. There is a spectacularly beautiful barber shop arrangement of "Shenandoah" which doesn't really come to life unless the singers take "liberties" with the tempo at several places. But, that sort of interpretive device is a characteristic of the style, and likely drives strict classicists crazy. So, I would say do the song in whatever style appeals to you. Make it your own!