The phrase to have two left feet means to be clumsy or awkward.

It is often used of an inept—usually male—dancer, as in The Man with Two Left Feet, a short story by the English author Pelham Grenville Wodehouse (1881-1975). This story was first published in the USA in The Saturday Evening Post of 18^th March 1916,  then in the UK in The Strand Magazine of May 1916, and finally in The Man with Two Left Feet and Other Stories (London: Methuen & Co. Ltd., 1917). The phrase occurs not only in the title of this short story, but also in its text:

He was now in a position to devote an hour a day to the lessons; and Mme Gavarni had said that that would be ample.
‘Sure, Bill,’ she had said. She was a breezy old lady with a military moustache and an unconventional manner with her clientele. ‘You come to me an hour a day, and, if you haven’t two left feet, we’ll make you the pet of society in a month.’
‘Is that so?’
‘It sure is. I never had a failure yet with a pupe, except one. And that wasn’t my fault.’
‘Had he two left feet?’
‘Hadn’t any feet at all. Fell off of a roof after the second lesson, and had to have ’em cut off him. At that, I could have learned him to tango with wooden legs, only he got kind of discouraged. Well, see you Monday, Bill. Be good.’
[…]
‘I thought I could do it. Oh, Lord!’ Misery was in every note of Henry’s voice. ‘I’ve been taking lessons every day since that night we went to that place first. It’s no good—I guess it’s like the old woman said. I’ve got two left feet, and it’s no use my ever trying to do it. I kept it secret from you, what I was doing. I wanted it to be a wonderful surprise for you on your birthday. I knew how sick and tired you were getting of being married to a man who never took you out, because he couldn’t dance.’

The phrase to have two left feet postdates the synonymous to have two left hands and to have two left feet and two left hands.

The adjective left has long been associated with inferior performance, awkwardness and even insincerity. This arose from the perception that the left hand was the weaker and therefore inferior, and from the corresponding use of the classical-Latin adjective sinister. Robert Allen gave the following explanations in Dictionary of English Phrases (Penguin Books, 2008), s.v. left-handed compliment:

Left-handed in this context is derived from the widely applied notion of left-handedness as awkward and even ‘sinister’ (the Latin word for ‘left’). […] The ultimate origin of the notion, and of the adverse associations of left-handedness, go back to the days of the Roman Republic, when divination by the haruspices involved examining the entrails of animals. If the liver was found to be on the left side of the body, the gods were expressing disfavour and the omens were therefore bad.

Likewise, English has borrowed from French:
– the adjective gauche—literally left—meaning awkward, tactless;
– the noun gaucherie—literally left-handedness—denoting awkwardness, tactlessness.

These are, in chronological order, the earliest occurrences that I have found of the phrase to have two left hands—most of the texts in which this phrase occurs indicate or suggest that to have two left hands is a loan translation from the French phrase avoir deux mains gauches:

1-: From the translation of an extract, about English women, from L’Angleterre vue à Londres et dans ses provinces, pendant un séjour de dix années, dont six comme prisonnier de guerre ¹ (Paris: Alexis Eymery, 1815), by the French army officer René Martin Pillet (1761-1816)—translation published in several British newspapers in December 1815, for example in The Courier (London, England) of Friday the 8^th:

The awkwardness of all, in dress and manner, being the same, it would be wrong to expect to distinguish the ranks of society by ease or decorum of manners. English women in general, no matter of what condition, are destitute of grace and taste, and one may literally say, that an English woman has two left hands.
     original text:
La gaucherie dans la tenue et la manière de se présenter étant les mêmes, on aurait tort de chercher à reconnaître les classes, les rangs de la société, dans les manières nobles ou aisées. Généralement, les femmes anglaises, n’importe la condition, sont dépourvues de grâces, de goût, de ton : on peut dire à la lettre qu’une femme anglaise a deux mains gauches.

¹ L’Angleterre vue à Londres et dans ses provinces, pendant un séjour de dix années, dont six comme prisonnier de guerre translates as: England seen in London and in its provinces, during a sojourn of ten years, six of which as a prisoner of war.

2– : From The Cook and Housewife’s Manual (Edinburgh: Printed for the author, 1826), by Margaret Dods, pseudonym of the Scottish author and journalist Christian Isobel Johnstone (1781-1857):

To carve quickly and neatly requires a good deal of practice, as well as vigilant observation of those who perform the office well. There are awkward grown-up persons, having, as the French say, two left hands, whom no labour will ever make dexterous carvers; yet there is no difficulty in this humble but useful art, which young persons, if early initiated under the eye of their friends, might not easily surmount, and thus save themselves much awkward embarrassment in future life.

3-: From a letter published in The Examiner (London, England) of Saturday 12^th July 1845:

One may sometimes see an unfortunate wight, who has been condemned to parade his untaught limbs in some stiff and formal circle, endeavour to mitigate the awkwardness of his two left hands, by sticking his thumbs into his armholes.

4 & 5-: From Chambers’s Edinburgh Journal (Edinburgh: William and Robert Chambers – London: William S. Orr):

4-: From The Duke of Normandy. A Romance of Real Life, published in Chambers’s Edinburgh Journal on Saturday 18^th October 1845:

M. de Talleyrand ² […] replied, with his usual epigrammatic irony, ‘There are some people who are born with two left hands. This is poor S.’s case: added to which, he seems to have been brought into the world without brains.’

² The French statesman and diplomat Charles Maurice de Talleyrand-Périgord (1754-1838) held high office during the French Revolution, under Napoleon I, at the restoration of the Bourbon monarchy and under King Louis-Philippe.

5-: From Words borrowed from the French, published in Chambers’s Edinburgh Journal on Saturday 20^th December 1845:

Gauche—‘The left’—the designation of the opposition in the French chamber of deputies. The extrême gauche, the appellation of the most ‘liberal’ of that party, which takes its position farthest from the tribune and seat of the ministers. These words have obtained a certain currency amongst us, to express the corresponding political sects of our own country. Gauche had, however, an acceptance with us from a time antecedent to the existence of these parties, being employed to describe those who, from want of handiness and tact in small matters, are always meeting with little misfortunes, as they are pleased to call them. When filling a lady’s glass, for instance, they spill the wine; in sealing a letter, they burn their own or somebody else’s fingers; they knock over vases, overturn inkstands; in the ball-room tread on cherished flounces; when asked to hold a bouquet, let it fall, and then most likely tread it to destruction. All these little accidents are called gaucheries; because, as Talleyrand observed of one of the class, ‘this sort of people seems to be born with two left hands.’ We have borrowed another expression for these unfortunates—mal-adroites.

These are, in chronological order, the earliest occurrences that I have found of the phrase born with two left feet and two left hands:

1-: From A Journey Due North, by the British author and journalist George Augustus Henry Fairfield Sala (1828-1895), published in Household Words. A Weekly Journal. Conducted by Charles Dickens (London, England) of Saturday 31^st January 1857:

I am naturally modest, not to say awkward, clumsy, and born with two left hands and two left feet, I do not mingle much with the gay throng, but retire within myself.

2-: From Memoir of a Brother (London: Macmillan and Co., 1873), by the British social reformer and children’s writer Thomas Hughes (1822-1896):

And so it was with all our games and exercises, whether we were at football, wrestling, climbing, single-stick (which latter we were only allowed to practise in the presence of an old cavalry pensioner, who had served at Waterloo). He seemed to lay hold of whatever he put his hand to by the right end, and so the secret of it delivered itself up to him at once. One often meets with people who seem as if they had been born into the world with two left hands, and two left feet, and rarely with a few who have two right hands; and of these latter he was as striking an example as I have ever known.