Interesting thread!

Latin and Greek poetry didn't rhyme, what stopped it being prose was that it fitted a preset metre. Greek was more successful in this, as the metric "feet" were more suited to the Greek mix of long and short vowels. Latin struggled with them because it had more long vowels and fewer short ones.

As has been mentioned, mediaeval poetry went in for a lot of alliteration. Rhyming seems to have come later. Rhyming in song doesn't really count for much unless the line lengths are in a fairly obvious pattern, otherwise the listener tends to miss it.

Khandu's reference to 'Like a Rolling Stone' is interesting, but those deal, meal and steal words are each rhyming with the next line: 'How does it feel?' rather than with each other.