According to Child, the oldest instance of something recognizable as Lord Randal is an Italian broadside of 1629 presenting a medley of songs which includes three lines of the ballad 'L'Avvelenato', which was still current in Italy during the 19th century. FJC gives no translation, but from his description 'L'Avvelenato' resembles Lord Randal very closely. The Scots and English examples are much more recent.

Bronson regarded 'Billy Boy' as a parody, and added it as an appendix to Lord Randal. The first two verses ("Where have you been all the day?" and "What did she give you to eat?") follow the Randal pattern, but after that it goes off somewhere else entirely. There doesn't seem to be much similarity in the tunes, either.

As Dave Mackenzie says, 'Hard Rain' is generally supposed to be based on Lard Randal, but I'm not sure of the source for that. I believe that Dylan did have a full set of Child Ballads on his bookshelves in Greenwich Village, so it's not unlikely.