Elephind and Google Books searches dig up examples of the expression going back to the 1920s. The oldest match is from Johnny Dope, "Squints at Sports," in the [Urbana, Illinois] Daily Illini (May 13, 1920):
Out of 21 starts the Detroit Tigers won six games. They can't win for losing.
From Making Paper, volume 9 (1926) [snippet view], which has the expression on page 180:
We have a little lady in our office who just couldn't win for losing. She didn't have to holler "come you 'leven." She always drew it.
and again on page 215:
Somehow Mr. Hanny couldn't win for losing.
Also, from "Canyon Splits With Warriors at Local Field," in the [Abilene, Texas] McMurry War Whoop (May 5, 1928):
"Can't win for losing." That seems to express the results the Warrior ball players have been meeting in their recent skirmishes on the [baseball] diamond. Canyon was successful in taking the first of a two game series here last week, although the tribe came back to win the second. Up at Tech this week, the tie was played off and the Torreadors proved the better. That 25-20 game, with the Indians on the heavy end, was a feature of the trip.
And finally, from "Temple Hard Luck School," in the Breckenridge [Texas] American (December 7, 1928):
TEMPLE [TEXAS], Dec. 7. (AP)—Temple is extolling a high school football team that "couldn't win for losing," which lost most of its important games, but which always gave the home town rooters a tremendous thrill.
In the eleven games which Temple played the Temple captain tried to call the toss of the coin every time—and failed eleven times. In every game that the team lost it gained more yards than its opponents. It won the only game in which it was clearly outplayed, on the basis of yards gained.
In its final game, the game which it most wanted to win, it outgained Waco in almost every department except scoring. For a few seconds the Temple defense wavered and Waco won, in spite of the fact that Temple had thrown the Waco team for almost as many yards loss as gain. The yards that Waco did gain were the ones right next to Temple's goal posts. Temple rooters are in favor of repealing the law of averages.
This last account suggests that an early sense of the expression was that the person or team that "couldn't win for losing" performed well in every facet of the task except succeeding in it. However, it may be that other early users of the term used it merely to mean that the person or team couldn't get out of its own way and was destined to lose because it simply didn't know how to win.
As other answerers and commenters have noted, "can't win for losing" has lots of companions in phrases that seem to express kindred sentiment—including the one featured in 1967 Sam and Dave song "I Can't Stand Up for Falling Down", memorably covered in 1980 by Elvis Costello.