The Traditional Ballad Index has an entry. Roud #3749. "...first printing appears to have been in one of the Tom Thumb songbooks (n. d. but c. 1790)." Not able to verify this in the few references that I have.
There is no evidence of the rhyme before the 18th century; the appended stories about Juana and Henry VII on the one hand and Prince Philippe on the other may have been concocted in the late 19th to 20th c.

More than one tune available; no evidence of these before the 20th c. that I can find.
The Opie's in the preface to "The Singing Game" say that "Many of the tunes are recognizably part of the common stock; and echoes of old and well-known airs can be heard in them: ....'I Had a Little Nut Tree'....." Perhaps this is why the tune is so familiar; I have heard it or a slight variant with several simple songs.
The Traditional Ballad Index mentions a tune by Linscott; don't know if this is the one found on some of the children's rhymes sites.

Not in W. W. Newell, "Games and Songs of American Children," (first printings 1883 and 1903; Dover reprint); Linscott's report of 1939 seems to be the first record of it in America. I would guess that this might be an oversight.

There is a copy of sheet music, "I Had a Little Nut Tree," in the James Joyce Sheet Music Collection, Miami University, Otto G. Richter Library; date and composer not given in the listing.