Here's another clue in the 'Away with Rum'-'North Atlantic Squadron' tune puzzle.
As posted above, 'North Atlantic Squadron' was published in 1931 in the book "Mud and Stars" where the tune was given as 'The Armormed Cruiser Squadron' or 'Away with Rum'.
According to the book "Mess Night Traditions" (2007, Charles J. Gibowicz), p.76, the 'Armored Cruiser Squadron' was connected to the banning of rum rations in the US Navy by teetotalling Josephus Daniels, Secretary of the Navy, in mid-1914:
"For one of the [New York] Tribune's cartoons, some verses had been composed to fit an old song of the times and these accompanied the cartoon. The verses became a hit and were popularly sung throughout the fleet.
Away, away with sword and drum,
Here we come, full of rum,
Looking for someone to put on the bum,
In the Armored Cruiser Squadron.
Josephus Daniels is a goose,
If he thinks he can induce
Us to drink his damn grape juice
In the Armored Cruiser Squadron."
(This book is available on Google Books.)
From this piece of information and the lyrics it might be deduced that 'Away with Rum' (complete with rollicking chorus tune) predates the 'Armored Cruiser'/'North Atlantic Squadron' songs. After Harrigan and Brahan wrote the original in 1882 it probably changed tunes and went into oral tradition - Randolph's informant was probably correct in dating 'Away with Rum' to around 1900. Certainly by 1914 it was being adapted and parodied itself.