I was considering having Miloš Obrenović retake the Serbian throne earlier, or simply retaining it outright due the effect of various butterflies on the country. But digging a little deeper, none of the divergences in this timeline should have had a major impact on them prior to the collapse of the Austrian Empire, so maybe Aleksandar Karađorđević still coming to power might make more sense here. Would a victorious Russia have any impact on Aleksandar's deposition?
I personally don't think it would, honestly. We're dealing less with issues of governance (which is still important, mind you), and more with issues of people and personalities. Heck, a victorious Russia could make things
worse, given how among the influential in Serbia we have Francophiles, Russophiles, Austrophiles, etc. However, there is one aspect that could possibly shift things significantly. Following the Crimean War OTL, at the 1856 Treaty of Paris, the Russian protectorate (read: protection of its rights and neutrality) over the country was expanded over the other signers, those of course being Britain, France, Austria, Prussia and Sardinia. Alongside that, the guarantee of freedom of commerce and navigation on the Danube was also important.
When the Tenka Conspiracy occurred in the fall of 1857, and failed, the Prince took the opportunity to strike against his Privy Council (of whom all but three were against the Prince, and some partook in the conspiracy) by making them resign due to being compromised (and if they didn't resign, they'd be arrested), despite not being involved. Six were specifically named to resign, those being Lazar Arsenijević, Stevan Magazinović, Jovan Veljković, Stojan Jovanović Lešjanin, Živko Davidović and Gavrilo Jeremić, which they did, while three more were considered compromised (including Aleksa Simić and Ilija Garašanin). Only four council members were considered safe, and we needn't mention the actual conspirators who were swiftly arrested and sentenced to life (originally death, until the Porte's intervention) upon the discovery of the conspiracy, leading them to Gurgusovac Tower in Knjaževac, where public opinion shifted on the convicted, going from loathing for what they had done (especially given a high-ranking official was at the head of the conspiracy), to sorrow for the cruel treatment they received in the tower's dungeon (to the point one of them died). With spots empty in the Privy Council, the Prince filled them all with loyalists.
The Prince had the opportunity to confirm his new power he had gained through law, but before he could, the trans-council opposition decided to appeal to the Great Powers and point to the fact that the Prince had carried out a coup d'état. OTL this resulted in France approaching Russia, interested in helping the Russians suppress Austrian influence in Serbia, as the prince's policies were Austrophilic. The two demanded the intervention of the Porte, in the same fashion they had done back in 1838 with Miloš and the Turkish Constitution. The Porte appointed Etem Pasha as commissioner to go and investigate, with the hope that they can be the ones to judge the situation, and avoid the Europeans sending one instead. Etem Pasha would go as far to threaten the Prince with his replacement, and thus, the Prince was forced to not only pardon the conspirators and hand them to Etem Pasha, but to also allow the deposed council members to return to the Privy Council. With momentum high, the opposition organized itself enough to convene the Saint Andrew Assembly, and finally replaced the Prince.
I'll say, first things first, I don't think there is a chance the conspiracy can succeed if it follows per OTL. They literally just hired some peasant from the Kragujevac area, Milosav Petrović, and just gave him what he needed to kill the Prince, but the man instead just went to Belgrade and began blackmailing the conspirators, taking upwards of 1000 ducats from them. And soon after, Milosav's brother-in-law found out and reported this situation to the authorities, leading to their imprisonment. The Porte's word might mean less now that their garrisons are out of the country TTL, but I imagine they'd still intervene to prevent the executions of the conspirators, thus leading to the same sort of shift of opinion that we saw OTL when they were sent to Gurgusovac Tower (which would just add further to the general dissatisfaction regarding the King, and further support for the return of Obrenović, whom unbeknownst to the populace had financed the conspiracy, while everyone else just thought Tenka wanted to establish a noble republic with him as its head). But the big change would be what would happen after the Prince decides to take advantage of the situation and fill the Privy Council with loyalists, since I imagine the other European powers not wanting Russia to decide alone (especially given the war just now), and while Austria may still have interests in Italy, I don't know if that would be enough to push France to get involved. And again, the Porte's slightly lessened influence due to the garrisons being out might embolden the Prince to stick it out, though dynamics may or may not influence what the opposition might do.
Given the circumstances, I still think it is inevitable that Aleksandar will be deposed, it's just that the process to it might now look a bit different. The writing was on the wall, so to say, you just need someone to interpret it because it reads like chicken scratchings.