The oft-quoted Shakespearian phrase, from Iago to Brabantio, goes like this (Othello, 1.1.115-117):
"I am one, sir, that comes to tell you your daughter and the Moor are now making the beast with two backs."
However, the term dates back to at least 1532 (Shakespeare was born in 1564), and can be found in François Rabelais', 'Gargantua and Pantagruel':
"In the prime of his years he married Gargamelle, daughter of the king of the Butterflies, a fine, good-looking piece, and the pair of them often played the two-backed beast, joyfully rubbing their bacon together..."
(Curiously, the evil wizard that terrorised The Smurfs was called 'Gargamel')
Rabelais used to be a Benedictine monk, believe it or not. It's entirely possible that Rabelais did not coin the term, and that it dates back through time immemorial; history does not record.