In Wkipedia's entry for Origins of rock and roll, we find this comment about Louis Jordan's song "Caldonia":
"Caldonia", first recorded by Louis Jordan and then by Erskine Hawkins and others, seems to have been the first song to which the phrase "right rhythmic rock and roll music" was applied, by Billboard magazine in 1945."
But the same article notes that Arthur Crudup had a hit rhythm & blues song titled "Rock Me Mama" a year earlier. And it reports that the term "rock and roll" supposedly appears in an Ella Fitzgerald song called "Rock It for Me" from 1937:
"Rock It For Me" was recorded by Ella Fitzgerald with Chick Webb and his Orchestra in 1937. Its lyrics mentioned a kind of music called "rock and roll": "Every night/You'll see all the nifties/Plenty tight/Swingin' down the fifties/Now they're all through with symphony/Ho ho ho, rock it for me!/Now it's true that once upon a time/The opera was the thing/But today the rage is rhythm and rhyme/So won't you satisfy my soul/With the rock and roll?"
And The Canadian Patent Office and Register of Copyrights and Trade Marks, volume 62, issues 9–12 (1934) has this as entry #11059:
- ROCK AND ROLL. Musical work. From Sidney Claire and Richard A Whiting to Irving Berlin Inc., New York, N.Y., U.S.A. 11th September, 1934–23rd November, 1934.
In connection with "rock and roll" as a form of dance, we have this intriguing note from E.J. Dackert, in The Postal Supervisor, volumes 26–19 (1935–1938[?]) [combined snippets]:
Six hundred Supervisors and friends of Branch No. 35 assembled in the Broadwood Hotel [in Philadelphia], February 8th, to celebrate the annual dinner dance. ...
Other special and noted features were "Joe" Dougherty doing the "Rock and Roll." Most of us did not know that "Doc" was a terpsichorean specialist prior to this evening. "Tom" McElwee's lecture as to where noise belonged was most interesting.
And here, earlier still, is an excerpt from Ethel Mannin, All Experience (1932) [combined snippets]:
The moment the tune ends the little woman withdraws her small white hand from the negro's big black one and returns to her table ; the negro bows politely and strolls away in search of a more interesting partner ; he finds a magnificent negress, a little over-rouged, a little overblown, but superb in her swagger and abandon ; they rock and roll and circle their hips together, thigh to thigh, stomach to stomach, laughing, given to happiness through richly sensual movement and insidious rhythm.
So it seems fairly clear that "rock & roll" was in use in a musical setting long before rock & roll music emerged as an identifiable genre or entity—and long before Alan Freed had a radio show to play music on. And of course, "rock and roll" as motions and sounds go back much further still, as a Google Books search amply illustrates. For example, with regard to motion, from Helen Jewell, "Questions," in Sketches in Purple, volume 2 (1901):
You jolly old Man in the Moon,
What do you find to see,
As you rock and roll in that golden bowl,
And the Winds sing a melody?
And with regard to "rock and roll" sounds, from Ethel Brooke Stillwell, "God's Playthings," in Outers'—Recreation (November 1920):
But oh, was ever anything to match a mass of thunder-heads in black and silver menace piled against a western sky?
With the play of leaping lightnings, rock and roll of crashing thunders, and the wind across the prairie like a river roaring by!
Many early references to "rock and roll" use the phrase to describe the motion a person feels on board a ship (as the OP notes) or a train, or on land during an earthquake. I imagine that the alliteration and brevity of the words rock and roll make them a natural pairing. In any case, people have been pairing them for generations—long before the first electric guitar chimed and the first teenager saw that it was good.