W. Lee 'Pappy' O'Daniel did to Johnson in '41 what LBJ would do to Coke Stevenson in '48.
He waited until he knew how many votes were needed to put him over the top, and then went to the county bosses he was allied to. In '41 O'Daniel had guys in the east of the state who 'found' the votes he needed. In '48 LBJ had county organisations along the border with Mexico (the Rio Grande valley) who delivered his winning margin.
LBJ later said that he lost the first race because he allowed his vote totals from his friendly counties released too early, allowing O'Daniels machine to do their business.
To change this result I think the only POD needed is for LBJ to decide he must be as ruthless as he would later be IOTL.
Johnson going to the senate before America is even in WWII is a fascinating what if. I started a TL where LBJ is elected at another special election straight after the ascent of Truman to the White House, and I had the very junior senator decide to use his talents to successfuly thwart the Taft/Hartley labor act, aka the greatest anti-New Deal reform passed by the Republicans before the age of Reagan. That's how significant I think an earlier Senator LBJ could be.