1240-1300
Albeit changes, small-scale, are already spreading elsewhere, there are really only three areas worth attention right now from an althistoric point of view. They are Eastern Europe, Middle East and China, all those (and some others, but that's beside the point) being spared the OTL Mongol conquest; ofcourse, Mongolia also was rather different, and interesting at that, so we will include it, China and Korea into the "Far East" section.
So anyway. While outside of those areas it basically means less panic and some minor psychological changes as well as tactical differences caused by the events in those three areas, while lands such as say Tibet were simply spared a Mongol invasion and lived on like they did in OTL before the Mongols. Now for the interesting bits.
Eastern Europe:
This was a tumoltous time, time of centralization efforts and the bloodshed that ensued. In Poland, Henry II of Lower Silesia allied with "the Germans" (which means that he allied with some of the German princes while getting the Holy Roman Emperor's approval of his actions, not that it really mattered but it was a nice propaganda card for Henry - "My words are backed by Imperial legions!") and with fire and sword, both his own and that of the Teutonic Order, united Poland and started ruthlessly wrecking the power of the magnates and other feudals; ultimately, this led him to troubles with the Teutonic Order, which he ultimately defeated and expelled from Thorn. Henry III eventually toned down on centralization and instead went for crusades - replacing the Teutonic Order, he succesfully crusaded in Prussia, conquering it eventually and forcefully baptising the Prussians. Elsewhere in Poland - not just in Silesia - in spite of all this plausibly anti-German activity (dismissing the Order, restricting the power of feudals, Germans included) German colonists were moving in large amounts, as after all it WAS getting crowded in HRE and the Silesian Piasts were always friendly towards German migrants.
Árpád Dynasty undergone a renaissance in Hungary under Bela IV the Great. Albeit he could not possibly reject the Golden Bull, he found it easy to outmaneuver it and to eventually modify it as to make himself de facto free to ignore the Diet most of the times. This caused a minor rebellion where, however, solidarity necessary to make feudals stronger then the king wasn't found and thus it was crushed. Thus, Bela was free to look elsewhere for expansion - succesfully campaining against Tataro-Cumans in Wallachia and against Premyslids in Styria. Eventually, he extended his power in the east all the way to Dniester and the Black Sea, whilst the Premyslids of Bohemia were thwarted with the defeat at Graz in 1265, after which Hungarian power, de facto if not de jure, expanded into the land sometimes called "Austria". Bela also had a rather costly failure of a foreign adventure elsewhere, but more on that soon. In 1271 Stephen V inherited the throne, but sadly died in 1278, albeit after crushing resurgent Bohemians at Vienna, forcing South Slav princes to his south to succumb to his supreme rule and made the Bulgarians cede their northwesternmost lands (most notably the city of Nish) after taking Sofia and threatening Philippopolis. Under the regency of his German wife Cathrine, his little son Bela V received good care and education, and Cathrine herself prevented the magnates and feudals from rising in power significantly during the Regency. In 1295, Bela V rose to full power.
Coming under the pressure from the Livonian Order (Teutonic Order by then went back to the Holy Land, seeing that there is not much to be gained in the Baltic), the Lithuanians were gradually pushed out from Lithuania and into Russia, where they ultimately caused a lot of trouble. Livonians themselves however suffered horrible casualties at the hands of the various Lithuanians and later were near-destroyed by a vast native rebellion, uniting Christians and pagans alike disgusted by Livonian brutality. As the Novgorodians were beginning to rattle their sabers on that side of Lake Peipus, the Livonian Knights, in 1242 (note - due to butterfly reasons, they survived longer then in OTL), humbly submitted to the supreme authority of... King Abel I of Denmark. Danish armies barely stopped the rebels and the Livonian Order, now as yet another vassal of the Danish king, was saved. Denmark entered a new age, an age of empire.
In Rus, the Tataro-Cuman raids (albeit not nearly as devastating as OTL Mongol ones) have greatly weakened the eastern principalities, such as Vladimir and Ryazan, while due to growing trade, Novgorod and Galicia-Volhynia emerged supreme. Notably, both had good leaders, but while in the former Knyaz ("prince") Alexander was quite powerless outside of military affairs, in the latter Daniil Romanovich was an absolute monarch. A cunning and able ruler, Daniil has, by 1240, eliminated much opposition within his two principalities, and established good relations with the European ruling houses. He invited foreign specialists and advisors and brought Galicia fully up to date. Prosperous, his lands were an excellent spring board for the ambitious Rurikovich whose goals were much higher then those of even his father, Roman Mstislavovich, conqueror of Volhynia. He wanted to unite all of Rus under his rule. Technically, taking Kiev might be a problem (which is why Daniil was hoarding Western siege engines and specialists), but aside from that, the only serious opposition was from Novgorod. Variably "Venice" or "Athens" of the North, Novgorod was a great mercantile emporium that was also formidable in battle on land and sea alike. Why, in the end of 12th century, Novgorodians and their Karelian vassals/mercenaries pulled a Viking on the Vikings by looting and burning down Uppsala, one of the richest Scandinavian cities. Needless to say, this did NOT contribute to friendly relations between two powers whose interests were in conflict in Finland - Novgorod and Sweden. And another natural direction for Novgorodian expansion, the Pribaltic, suddenly turned out to be... Danish. How's that for a Scandinavian conspiracy? But this conspiracy has evidently failed to crush Novgorod; the Danish allies in Pskov were utterly defeated at, well, Pskov, the Danish-Livonian knight army was decemated at lake Peipus, the Swedish army was defeated at river Narva (Alexander since then was called Narvskiy). All that happened in 1243-1245; in 1246, the Scandinavians decided to launch a new offensive. But they needed allies...
Daniil Romanovich would have been a good merchant. His idea of cooperation with the Scandinavians was such: "Alright, I will let you have your little Finland/Livonia all for yourself, and will give you trade priveleges in Novgorod when it is mine. In exchange... you will lend me military and monetary help as required for me to unite the Rus." Scandinavians laughed at this. Then suddenly the Novogorodian fleet decimated a Swedish one at Abo, and things got... not as hilarious for the Scandinavians. So they agreed. And Alexander Narvsky soon had to face a massed Galician army which rushed through Danish lands in Lithuania and soon was knocking at the gates of Pskov. Novgorodians were soon after defeated at Ilmen Plain, but Narvsky kept the army in good order and won a few victories afterwards.
And then Novgorod proved its title of "Athens of the North" by sending Alexander into exile. Danish-Galician armies converged at Pskov and again besieged Novgorod; the city eventually fell and was burned down, Finland (and Karelia) was declared Swedish, Daniil was acknowledged as the Knyaz of Pskov and of (rebuilt) Novgorod. Alexander Narvsky started a peasant uprising, but was eventually defeated. Later, in 1254, a few other Russian princes, having secured the assistance of Bela IV of Hungary who had a dynastic claim on Galicia, tried to conquer Daniil's northern enclave of Novgorod and Pskov (and associated areas). Galician armies - as promised, reinforced by the Danes and the Swedes - soon enough took Minsk and Kiev. Hungarian armies besieged Lvov and Galich and actually took the former, but were handled a horrible defeat at Zbruch. Pereyaslavl surrendered without a battle; Smolensk after some minor skirmishes. Vladimir, Ryazan and Chernigov remained, however, and their armies nearly won in the decisive battle at Moscow in 1259. But just as Galician defeat seemed certain, as reinforcements arrived from the south, preventing a succesful rout of the Galicians, and eventually the Three Knyazes were fought to a standstill by Daniil. He eventually retreated from Moscow, but his army was not more damaged then that of his enemies, while he, unlike them, had many reserves. In 1260, Daniil attacked Vladimir itself and in a quick, decisive assault took the seat of the Velikiy Knyaz. Rus was united five days later, as the Three Knyazes surrendered at Vladimir.
An interesting feature of this newly-unified Rus was the efforts of Kings (for the lack of a better name) Daniil I and Roman I (the first of Rus; the second of Galicia-Volhynia) to reconcile the two churches. They bore no great fruit yet, but as Catholic influence spred into Rus through the already pro-Catholic Galicia it seemed likely that Rus at least could be won for the Pope. Other then that, the rest of Rus' history in this period was a peaceful era of quiet prosperity and not-so-quiet conflict between the korol' (king) and the boyars.
The Tataro-Cumans during this time were rather disorganized and in this fashion continued raiding Rus and harassing Hungarian-German colonies in Wallachia and Moldavia.
Middle East:
Shaken as Khwarezm was by the Sugubid invasion of 1222, it lingered on until 1251, albeit wrecked by open rebellion. An Assassin (with a capital "a") assassinated (what else are assassins supposed to do?) yet another sultan, and Khwarezm, once powerful, now was completely unexistant. As Seljuk Turks to the northwest regrouped and joined the struggle and as the Abbasid Caliph got his hands dirty as well in the effort to restore his greatness, complete chaos was guaranteed allowing the Ayyubids in the west to decimate the Crusaders, who were by then led by the ambitious and capable new Teutonic Order grand master Hermann von Hohenzollern. Hermann put his eyes on retaking Jerusalem, and his great military skill allowed him to do that; but taking it proved harder then holding it, and thus eventually the Teutonic Order was destroyed in the battles raging around the Holy City, and by 1260 the Crusaders were utterly beaten. The Holy Land was in the hands of the Faithful. A brief civil war in the Ayyubid realm begun in 1278 partially on the grounds of the exact definition of who was faithful and who not (and also who was more equal from amongst the equals, now that we're at it) and, much more significantly, of who should rule the Faithful now that they rule the Holy Land. Mamlukes, who there opposed the Ayyubids, were eventually defeated and abolished and subsequently massacred, and by 1283 the Ayyubids, led by al-Khalid, were undergoing a true renaissance in most senses of the word.
Further north, the Turks of the Sultanate of Rum were ever-expanding. Kay-Khusraw III inflicted defeat after defeat on the Empire of Nicea in 1240s, and indeed this - along with the exodus of the surviving Crusaders since 1260 to Constantinople and the Bulgarian expansionism in Thrace - allowed the survival of the midget Latin Empire... for now. Turks secured much of Anatolia, but faced defeat in a war with Trabzond in 1277. The small mountainous state itself was nearly-overran, but the Turks forgot the dynastic ties between Trabzond and a great regional power - Georgia. Despite some minor dynastic strife just before that war, David III still had at his disposal the fearsome highlander armies of Georgia that had already a healthy tradition of fighting back Turkish armies in mountainous conditions. The Turks were defeated, and direct Georgian rule was extended to Trabzond, which previosuly already was a Georgian vassal - during the reign of Queen Tamara. Using the weakness of Georgia's other neighbours, Georgian power also, under the rule of David IV, extended all over Transcaucasia and expanded into formerly-Seljuk Kurdistan (the Seljuks being distracted elsewhere as they were).
Khwarezmi Wars ended in 1286. By then, pretty much everybody in Middle East got involved to a degree, Assassins got wiped out, the Ayyubids conquered Iraq and instated a puppet Caliph, while in Persia and Central Asia a Turkish dynasty, the Kemalids, come to power. Kemalid power is reinforced by an army assembled from steppe nomads in Central Asia (not Mongols, simply other Turks, most of whom were Muslim anyway by then). The Kemalids soon came into conflict with the Sultanate of Delhi...
Far East:
Juchid Mongolia might seem rather weak to some. A part of its army has defected and created the short-lived Yuan Empire in northeastern China. Roughly half of what remained followed Sugubei west. But the remnants, perhaps paradoxically, were stronger then OTL Mongolia largely due the fact that were not spread out practically everywhere in the Eurasian Steppe. Rather, they were centralized, strenghthened and also took over old Liao and Jin cities. Ofcourse, much of the Jin lands were now held by Song China, but the northeast, including Dading, was Mongol. The Juchid power was centered in the city of Karakorum, but further south, in Manchuria and northeastern China, was the most prosperous part of Mongolia, and a one from which the Chinese cultural influence spred amongst the Mongols. Mongols also occasionally raided Song territory; a "raid" in 1259 was more of an invasion during which humiliatingly three Song armies were utterly routed and the Emperor himself was captured. Chia Ssu-tao, the chief councillor, had to pay huge tribute to get the Mongols out of China; this experience and the following demands of even more tribute, persuaded the new emperor, Chi-tsung, as well as Chia Ssu-tao, to start an overhaul of military structure. The Song Dynasty never did, like the Tang one, become a militaristic one, or indeed never actually made its army particularily strong, but these reforms gave it a fighting chance.
But the main Mongol effort was not directed towards China in the time; no, in 1278 the Mongols stormed into Korea. Koreans resisted bravely, but were crushed; Mongolia now stretched from Dzungaria to Cheju. And Mongolia leaned with a menacing presence to the north from China. The Mongols also tried to invade Japan, but their fleet was not a very good one and thus was damaged by the storms and what little Mongol forces survived were crushed on the coast. Khan Tachi was killed in the battle, and this has put Mongolia back somewhat, as a civil war ensued. But by 1300, it was clear that the cunning, Chinese-assimilated Darchai would win.
China, meanwhile, was somehow revitalized by the humiliation of 1259. Not only was the army reformed, but Emperor Chi-tsung was also determined to take matters into his own hands. A vigorous reformer, he, well, reformed the Chinese buerocracy. At the same time, China also "opened up", not that it was ever in particular closed. What I mean is that the combination of such factors as increasing maritime trade and the heretofore unprecedented placement of a capital in a port city caused Song China to actually develop a fleet. It hardly had an agressive drive needed to put that fleet to a good use; but still, the growth of maritime trade and of contact with India itself (not very active, but still, a contact) would be a foreshadowing of things to come. Perhaps even more serious was a rare show of force under Emperor Kon-tsung, the conqueror of Taiwan, who, AS ONE MIGHT EXPECT, conquered Taiwan for some obscure reason (many believe that he wanted to get rid of an ambitious general who afterwards was put in charge of Taiwan as a governor). This has caused an unsurprising amount of controversy, but the "lets evacuate Taiwan and pretend nothing happened" faction was barely persuaded that Taiwan was a part of China, really, being so close and all.
The ocean-going vessels were already quite widespread in China when in 1297 Mu'lan-pi was officially discovered. It is believed that Chinese ocean-going ships possibly came there before, but either way, not much of a trace remained; this time, however, it was known that far to the east, there is a very long island. The "shrug and say "So what?"" faction prevailed at first, but in 1299, the Emperor ordered a new expedition east, "out of scientific interest" (not exactly how he put it, but anyway). These scientific purposes were more like looking for more animals/plants for the zoo/garden, as well as checking if there are spices of immortality there or anything else of the kind.
and i don't like all these comments about me being obsessed with china 
so i'll need the long time to do stats and etc to prepare for the beginning of that nes when continuation closes. 
