There is leeway in what "steady paycheck" means, but the common interpretation would be a consistent (1 yr+) full-time employment or profitable business, that is sufficient on its own to support an adult. You can conceive of an alternative definition, but that seems to be the one used by Politico.
Politico's article is by far most in-depth research on Sanders' pre-1981 employment history, and despite it being the author of the claim, I will still cite a few of its primary-source details. Note that its actual claim is slightly different than your question title; it claims no steady job until "pushing 40", not "40", as Sanders was 39 when he obtained a steady $33,800/yr paycheck as a mayor.
Politifact was unable to find definitive independent proof either way:
After graduating from the University of Chicago in 1964, though, Sanders did work a series of odd jobs before his political career began. Some of the positions he held include: an aide at a psychiatric hospital, a freelance writer, a preschool teacher and a carpenter.
Many of these jobs were likely part time, as Sanders ran for office a few times before winning, but we could not find evidence that proves none were full time, either. And the Sanders campaign did not respond when we asked if any of these jobs were considered full-time positions.
Snopes' analysis was similar:
After receiving a Bachelor of Arts degree in political science from the University of Chicago in 1964, Sanders primarily worked a series of odd jobs while attempting to get his political career off the ground
(Both sites chose to rate a more aggressive claim that Bernie "never had a 9-5 job", which they ultimately found to be false based on his political jobs starting at age 39. Though from their reasoning and counterexample I infer they'd rate this as unknown or true.)
Bernie Sanders certainly never had much money prior to 1981:
"I never had any money my entire life," Sanders told Vermont public TV in 1985 [age 44].
"The electricity was turned off a lot," [neighbor] Barnett said. “I remember him running an extension cord down to the basement. He couldn’t pay his bills.”
"He was always poor," Sandy Baird, another old friend, told me in Burlington.
"Virtually unemployed," said Nelson, the political science professor at the University of Vermont.
"Just one step above hand to mouth," said Terry Bouricius, who was involved with Liberty Union.
Sanders' work experience is on his 1980s resume:
His carpentry career wasn't a steady paycheck.
He worked some as a carpenter, although "he was a shitty carpenter," [Liberty Union Party member] Bloch told me. "His carpentry," [Liberty Union Party member] Morrisseau said, “was not going to support him, and didn't."
His writing career wasn't a steady paycheck.
The Vanguard paid as little as the rest. "It would’ve been not more than 50 bucks," said Greg Guma, a former editor. Vermont Life? "Our rate was 10 cents a word," said Brian Vachon, a former editor.
Politico characterizes his teaching, psychiatric hospital, and state jobs as temporary:
He bounced around for a few years, working stints in New York as an aide at a psychiatric hospital and teaching preschoolers for Head Start [a federal low-income program], and in Vermont researching property taxation for the Vermont Department of Taxes and registering people for food stamps for a nonprofit called the Bread and Law Task Force.
While I cannot find evidence of the time periods, Sanders listing "Freelance Writer, Carpenter, Youth Counselor, State Employee" on a single line on his already brief resume suggests that none of these were consistent, full-time, or complete on their own.
He had a nonprofit film business for five years but it also didn't seem to be a "steady paycheck":
He started a business out of 295 1/2 Maple, making low-budget films about people, places and events in Vermont and New England history that he felt were getting short shrift in the region’s schools.
He priced it at $200 or offered it for rent for $35. He drove all over, like he had running for Liberty Union, inviting himself into schools, meeting people and trying to persuade them to listen.
Admittedly, Politico may be using pessimistic phrasing to support its claim, but independent film production is hardly known to provide a steady income.
Sanders did receive unemployment benefits, which necessarily requires some sort of previous employment. However, the qualifying job was temporary or inconsequential enough that apparently Sanders couldn't recall what it actually was.
[Sanders spokesperson Michael Briggs] said Sanders received unemployment, "for a few months," in 1971, though Sanders can't remember what the job was that qualified him for the benefits.
Sanders graduated in 1961 from the prestigious University of Chicago, currently ranked 6th nationally by U.S. News and World Report. That is to say, if Sanders had wanted a 40 hr/wk job, he certainly had the credentials to obtain a decent one.
But it would seem that full-time work was simply not compatible with his interests or direction.
"His work was to be a politician,” [magazine editor] Guma said. “He put everything into what he was doing.
"I don’t know what he did for money," [Liberty Union member] Troville said. "Everything was always campaigning. Everything was always organizing. Everything was always writing."
"He was totally involved in his attempts at running for office," [acquaintance] Marvin Fishman, who knew him at the time, told me on the phone.
Liberty Union “people found it difficult to support themselves while engaging in full-time political work,” Michael Parenti, one of those people, wrote..."Some held jobs that allowed free time for campaign activities, while others lived off unemployment insurance."
There is significant but nondefinitive evidence that Sanders preferred political activity to steady employment, to the extent that he never had a "steady paycheck" until his first full-time political job at age 39.
Update (March 2020)
CNBC investigated this matter after Democratic rival Hillary Clinton leveled a similar accusation in her Hulu documentary.
[Sanders] was a career politician. He didn’t work until he was 41 and then he got elected to something. It was all just baloney, and I feel bad that people got sucked into it,
Unfortunately, they found no different information than I've summarized here. Unless Sanders releases contrary details, I suspect the answer will remain speculative.