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.
The Snowclones Database 
From http://www.etymonline.com/index.php?term=have
Phrase have (noun), will (verb) is from 1954, originally from comedian Bob Hope, in the form Have tux, will travel; Hope described it as typical of vaudevillians’ ads in “Variety,” indicating a willingness to perform anywhere, any time.
Personally I’ve heard “Have X, will Y” a few times, but not with Y being travel.
I’m familiar with this phrase from the 1959 song ‘Have Love, Will Travel’ by the Sonics.
http://en.wikipedia.org/wiki/Have_Love%2C_Will_Travel
My first encounter with this was the Heinlein novel, so it took a while for me to actually understand the “will travel” part as “will[ing to] travel” instead of “[it] will [enable me to] travel.”
For some reason I also think of this as a Victorian newspaper advertisement sort of phrase, but that might just be due to the TV series.
I know this term as ‘have suitcase, will travel’. I assumed it was maybe a depression era plea for work (‘will work for food’, if you will).
Pingback: "Have X, will travel" - what kind of grammar is this ~ English Language & Usage ~ AnswertoWorld.com