1954 was the earliest attestation I could find, but it probably goes back further. The expression was popularized first by Bob Hope’s 1954 biography Have Tux, Will Travel and then by 1950s TV (and radio) show “Have Gun–Will Travel.” The title of Robert Heinlein’s 1958 Have Spacesuit, Will Travel was taken from the show.
Variations of X: music (seen on a shopfront in my hometown), laptop, children, fingers. I think singular nouns are more common than plural nouns in the X slot.
Thanks to commentator mollymooly for the earlier reference.