Q: Was there a similar phrase in vogue before chewing gum became popular?
The phrase can't walk and chew gum at the same time is often used to describe someone who's clumsy, uncoordinated or stupid, and there are many idioms for this: can't tell one's arse from his elbow, all thumbs, butter fingers, ham fisted, klutz.
There are also other phrases that mean it's impossible to do multiple things at the same time, but these are usually "defensive" rather than "insulting", such as having your cake and eat it too (recorded in 1546 as wolde you bothe eate your cake, and have your cake?) and the Yiddish can't dance at two weddings [with one behind/pair of feet].
Another multitasking phrase with yet another meaning is to have one's finger in too many pies, for a person who is able to multitask, but is overdoing it.
Q: when did walk and chew gum enter the lexicon?
It can be found in a May 1966 snippet of the US Marines' The Leatherneck, quoting Sgt Jerry Necaise:
"In fact, I had a man in my squad who was so uncoordinated, he couldn't walk and chew gum at the same time. But, after two weeks in Canada, he was skiing like a pro!"
According to The Big Apple it can be earlier found in a Texas newspaper:
24 December 1956, Denton (TX) Record-
Chronicle, sec. 2, pg. 2, col. 4:
A classic comment by a local basketball
player referring to a teammate’s co-
ordination: “He can’t walk and chew gum at the same time.”
The same site believes the phrase comes an earlier "talk and chew gum".
Q: Is it true that this is a sanitized version of Lyndon B. Johnson's description of Gerald Ford? (The original purportedly had "fart" instead of "walk".)
Yes, but the walk version was around before Johnson's fart version. From the Guardian's Gerald Ford obituary:
One of his few deviations from the classic rightwing agenda was to support Lyndon Johnson's civil rights legislation. But that did not save him from the presidential quip (later sanitised for a prissy American public) that "Gerry Ford is so dumb he can't fart and chew gum at the same time".
And Wikipedia:
As Minority Leader in the House, Ford appeared in a popular series of televised press conferences with famed Illinois Senator Everett Dirksen, in which they proposed Republican alternatives to Johnson's policies. Many in the press jokingly called this "The Ev and Jerry Show". Johnson said at the time, "Jerry Ford is so dumb he can't fart and chew gum at the same time." The press, used to sanitizing LBJ's salty language, reported this as "Gerald Ford can't walk and chew gum at the same time."