The lyrics Fergie posted are recited with (IIRC)some other cool riddles on Steeleye Span's "Now We are Six" from the mid '70s.

The Wisconsin Journal of Education, III, 1873, has:

White bird, featherless,
Flew out of Paradise,
Sat on the castle wall.
King came, footless,   
Took it up, handless,
Ate it up, toothless,
Rode away, horseless.

The earliest printing of the words ending with "to the King's white hall" seems to be in The Gentleman's Magazine (London)1881. It's identical to the Steeleye version except that 'Lord Landless" is "Lord John Landless," which unfortunately doesn't scan.

I don't have the Opies' book on English nursey rhymes handy. It may contain further info.