Okay, the first question is who would have filled this roles played by each of these characters. Figure that of the three, Stalin is the one that emerges earliest.
Without Stalin, Leon Trotsky probably gets the nod as Lenin's successor. Trotsky isn't a Stalinist monster, although his shoot all deserters attitude in the Red Army and his political views were not as moderate as some claim today. Under Trotsky, the Soviet Union emerges as a left-wing dictatorship that has an axe to grind against followers of the old order, but without the pure hatred and terror that Stalin brought to power. Trotsky, however, is a true internationalist. He would not miss opportunities like Bela Kun rising in Hungary--indeed, Trotsky might be a worse leader than Stalin in terms of his desire to spread Socialism around the world. Less thuggish but More internationalist, I can imagine the Cold War starting very early on with Trotsky in control.
Meanwhile, Mao is essentially on the fringe of Chinese politics until after the Chinese Civil War. Zhou Enlai, as Moscow's "man" in china, might emerge as a Trotskyite ally against Chiang Kai Shek. With more vigorous support from Leon Trotsky in Moscow, its an open question who much the balance of power shifts against the Nationalists at any time. Chiang is probably faring worse than historically, probably because the Soviets are doing more meddling in China. Japan and the Soviets might agree to partition China, in which case Chiang is doomed. More likely, however, Japanese Expansion into Manchuria is opposed by the Soviets, possibly leading to a rematch of the Russo-Japan war.
In Weimar Germany, a small fringe party--The National Socialist German Worker's Party--never transitions to the political right. Instead, dominated by the Strassor Brothers and other left-leaning elements, it becomes one of the many forces joining the German political left. Unfortunately for the Weimar Republic, the political right remains divided and the political center is polarized. Against a more or less unified KPD, a motley assortment of monarchist, conservative and fascist parties emerge, some of them led by people who would have been Nazis had a small political party found a great speaker to lead them. The German Political Right clings to power until 1934, when president Hindenburg dies in office. But the extremely unpopular Kurt von Schliechter and his predecessor Franz von Papen lack the real means to energize the political right, which finally loses control to the state--into the hands of Ernst Thallman.
What emerges from the ascendancy of these characters is an incredible three power alliance--Germany, the Soviet Union, and China. Right wing revolutionaries might gain power in the face of these threats, such as Mussolini and Mexetas, but the Commintern would be much more expansionist and outgoing then ever before.
What follows is an a reversal of the 1940s situation--Communist Imperialism, where Western Democracies have to swallow their pride and team up with right-wing strongmen to win the war. And the Communist threat scores incredible victories. First, in Spain, Juan Negrin Lopez succeeds in defeating Franco, due in large part to major intervention from the leftist world powers. But the world drive to Communism would achieve a greater victory. With an electorial victory in Germany, Trotsky can begin to move in Eastern Europe. The Baltic States annexation into the Soviet Union was a naked threat of force. The Finnish annexation into the Soviet Union was a naked use of Force. The German Revolutionary government of Ernst Thallman was hell-bent on spreading socialism around the world, and this is exactly what they tried to do. Local Strongman Engelbart Dolfuss would be their first choice for elimination, but this would bring the Germans into a fight against Italy and Hungary. Meanwhile, the Soviets moves against Romania were likely to provoke a war from Poland as well.
It is in the face of these actions that Winston Churchill--a loud anti-communist leader--becomes the Prime Minister of the UK. This is not to say that the UK has been treading an easy line on these leaders. Neville Chamberlain had laid the framework for alliances with right wing dictators, working with Mussolini to keep the peace in Austria. Churchill, however, was far more willing to fight.
It's a fight of an entirely different nature, between the UK, France, Italy and Germany, and the three way fight in East Asia would not be easily resolved. Ultimately, the allies tried to patch up relationships between Japan and China and hope that Enlai and the Zet Armiya could not seize control. It would lead to an entirely different aftermath as well, with a world filled with right wing dictators and democracies attempting to appeal to leftist revolutionaries for support...