The term rooster is derived from the noun roost an Old English word (hrōst) that referred to the wooden spars of a hen-house roof. Oxford Living Dictionaries define a roost as a place where birds regularly settle or congregate to rest at night, so the roof meaning has been lost.
The precise origin of roost is unknown, but it is responsible for the metaphorical expression to rule the roost; to tyrannize over the poultry yard as a cock is wont to do. The idiom is nowadays reserved for any man or woman who makes the big decisions in any company, group or family. Etymonline claims the phrase is recorded from 1769.
Thus a rooster is the bird that roosts, and rules over the roost.
"Rooster" was originally shorthand for "roosting bird," preferred by the Puritans to the double
entendre of the more typical "cock."
The Etymology of Chicken, Cock and Other Fowl Words
It's worth mentioning that the Puritans were a group of English Reformed Protestants in the 16th and 17th century who sought to "purify" the Church of England from Roman Catholicism. Between 1629 to 1640, over 20,000 Puritans fled persecution in England to settle in the new world. They wanted to create a "nation of saints", based on virtue, “as a city upon a hill”.
As the OP correctly annotated, the slang meaning of cock was well established before the Puritans had began fleeing to New England.
This is only speculation on my behalf, but perhaps the Puritans were familiar with an English (bowdlerised?) term roost-cock. The earliest instance, according to Google Books, is dated 1754, the following excerpt is taken from a Greek-English dictionary called Lexicon Aristophanicum: Graeco-Anglicum
Another example of usage, this time dated 1791, is seen in the following biography entitled: Essay on the life and character of John Lord Somers, Baron of Evesham
... by the superstitious people in the neighbourhood, that the good lady, his aunt Blurton, walking with him in her hand, when a child, amongst her poultry, a beautiful roost-cock flew upon his head, and crowed three times with peculiar energy.
This usage seems an attempt to circumvent the vulgar meaning of cock, and because its author, Richard Cooksey, chose not to use the term rooster this seems to suggest that the American English equivalent, dated 1772, was either unfamiliar or completely foreign to Britons living in that period.
The following passage bats rooster firmly in the American ballpark, but links its coinage to Victorian values.
The Victorian era saw a great growth of absurd euphemisms in England, including second wing for the leg of a fowl, but it was in America that the thing was carried farthest. Bartlett hints that rooster came into use in place of cock as a matter of delicacy, the latter word having acquired an indecent significance, and tells us that, at one time, even bull was banned as
too vulgar for refined ears. In place of it the early purists used cow-creature, male-cow and even gentleman-cow. Bitch, ram, buck and sow went the same way, and there was a day when even mare was prohibited. Bache tells us that pismire was also banned, antmire being substituted for it.
The American Language by H. L. Mencken, first printed in 1919. Wikipedia informs me that the author was an American journalist, satirist, cultural critic and scholar of American English