The French is, etre assis entre deux chaises, literally, to be seated between two seats, and the meaning, as in English, is to fail through lack of decision.
It cannot be determined, but the French is probably the older saying, the English no more than a translation. The earliest English record is in John Gower’s Confessio armantis, of 1390, “Betwen tuo Stoles lyth the fal, Whan that men wenen best to sitte (Between two stools lieth the fall when one thinks one is sitting best).”
The allusion is, of course, to the concrete fact: a man seeing a seat at his left rear and one at his right rear, is likely to miss each of them.