Here's another piece of the puzzle:

One of the posts near the start of this thread mentions that 'The North Atlantic' might derive from 'The Old Destroyer Squadron'. A google search has turned up this - The Old Destroyer Squadron - from the 1931 book 'Mud and Stars - An Anthology of World War Songs and Poetry (ed. Dorothea York), pp.41-42. It was reprinted from an earlier book called 'The Book of Navy Songs', first published in 1926 by the Trident Society and the US Naval Academy at Annapolis. Here is the song in a later reprint, copyrighted to 1926, with tune (pp.40-41): The Old Destroyer Squadron (1926)

Most importantly, the tune is given by York as 'The Armored Cruiser Sqadron' or 'Away with Rum'! Meaning that 'Away with Rum' (with the popular chorus tune) goes back to 1926 at least...

(BTW: The google book links I've made don't seem to link to the specific pages, but I've given the numbers so it should be easy enough).