The phrase to sell sand in the Sahara and its variants refer to the supply of something to a place where it is not needed—synonyms: to sell refrigerators to the Eskimos and to carry coals to Newcastle.

In particular, could sell sand in the Sahara and its variants are applied to efficient salesmen, and, by extension, to persuasive persons—antonyms: couldn’t organise a piss-up in a brewery and unable to run a whelk stall.

These are the earliest occurrences that I have found of the phrase to sell sand in the Sahara:

1-: From the account of a session of the Louisiana Senate, published in The Times-Democrat (New Orleans, Louisiana) of Friday 29^th November 1907:

Upon which followed a debate of twenty minutes, eighteen of which were used by Mr. Millsaps, and in which the Senate accomplished about as much business as a man selling sand in Sahara.

2-: From The Woman in the Case, a short story by Lilian Bell, published in The Evening Chronicle (Charlotte, North Carolina) of Thursday 7^th January 1909:

“Jeff,” said the old man, “I’ve had words with Horace and cut him off without a cent—turned him adrift to earn his own living. He hasn’t a dollar; he never has made one and never can. […] What the devil are you laughing at?”
“Laughing, sir? Why, at the idea that ‘Tubbs’ can’t make money! Why, Mr. Gorman, at Princeton he was our ways and means committee. Horace Gorham not know how to make money! Why, he could make money in the Desert of Sahara selling sand to the natives! Old ‘Tubbs’ could sell shoestrings to a man with two wooden legs. Why, he was the whole finance committee of the Athletic Club! He could— Why, he was the cleverest man in the class!”

3-: From the column Rank and File, published in the Nashville Tennessean and The Nashville American (Nashville, Tennessee) of Sunday 24^th August 1913:

Joe Kearney and Walter Dismukes, with the Brandon Printing Co., spent a few days in the house last week. Joe and Walter keep such a close watch on each other that when one finds the other is in he comes in also. It is said that these boys could sell sand to the inhabitants of the Sahara desert.

4-: From The Evening Star (Washington, D.C.) of Tuesday 2^nd September 1913:

Financial Gift.

From the Boston Transcript.
The Washington lobbyist who admits that he has been making a good living selling public documents grafted from congressmen is the kind of genius who could go out to the Sahara and sell sand to the Arabs.

5-: From an article about Fielding Harris Yost (1871-1946), coach of the Michigan University football team, published in The Chicago Daily News (Chicago, Illinois) of Tuesday 8^th November 1921:

In Yost’s dreams, however, it is to be doubted if he ever pictured the confusion of scores and percentages which this year makes it about as easy to select the “champion” of the United States as it would be to sell sand in the Sahara desert.

6-: From How the Potato Peddler Became Mayor of Busy, Big Youngstown, O., published in The Philadelphia Inquirer (Philadelphia, Pennsylvania) of Sunday 8^th January 1922:

“Why, that fellow could sell refrigerators to Esquimaux.” You have often heard someone thus refer to the selling ability of some individual, but you probably didn’t believe that the man referred to could actually do it.
Out in the flourishing Middle West city of Youngstown, Ohio, there is a man who could not only sell refrigerators to Esquimaux, but who could also sell them a year’s supply of ice to boot. His name is George L. Oles and he is the newly-elected mayor. […]
[…]
The astonishing element in Oles’ election is not the fact that he was once a potato peddler, but how he got himself elected.
Applied psychology, finding the universal human note, that touch which appeals to human nature in everybody, and striking it through the medium of newspaper advertising—that was what elected Oles.
[…]
Oles’ advertisements were masterpieces of human appeal. Any one who reads them cannot doubt his ability to sell refrigerators to Esquimaux or radiators in the Sahara.

7-: From Selling and Buying, published in The Muncie Evening Press (Muncie, Indiana) of Saturday 13^th September 1924:

A good many failures are occasioned in the selling game by going at it from the wrong angle. You may need money but that fact does not concern one who is to buy you or buy from you. You must show your buyer that he can make a legitimate profit by following your selling suggestions.
And you must know your market. A good many failures are caused by those who would sell sand to the Sahara Arabs or start ice plants in the Arctic circle.

8-: From Do You Know These Men? New Cross-Person Puzzle Game, published in The Bakersfield Californian (Bakersfield, California) of Saturday 6^th June 1925:

The idea of the puzzle is to run through the list of names appended to this story and see if you can select the man to fit the description:
[…]
No. 12. Has a car for every member of the family but the dog and is contemplating roller skates for the dumb brute. Could sell sand on the Sahara to the Spanish army. Knows his oil lands.

9-: From The Fun Shop, consisting of jokes, humorous anecdotes, etc., sent by readers, published in several U.S. newspapers on Friday 19^th February 1926—for example in The Anaconda Standard (Anaconda, Montana):

A Gritty Sheik.

“Is he a good salesman?”
“Is he? He could sell sand on the Sahara desert!”—Glen Perrins.

10-: From the cinema column written by Grace Kingsley (1873-1962), published in The Los Angeles Times (Los Angeles, California) of Thursday 10^th November 1927—Richard Dix (Ernst Carlton Brimmer – 1893-1949) was a U.S. actor:

Richard Dix on Location.
Believe it or not, the first shots of Richard Dix’s new Paramount starring vehicle, “The Traveling Salesman,” will be shot on the Mojave Desert. Just what Mal St. Clair, the director, has in mind, isn’t certain, but it is possible he means to illustrate the old saying about a salesman being so good that he can sell sand on the Sahara.