The "old" religion, which itself was largely reinvented as the Romans picked up more and more Greek influence, was on its way out for sure; no one, at least no one of the ruling classes, believed in it any more, the question was, what to believe in instead?
This is how the problem looked in ruling circles--it might well be that simpler folk in the countryside remained believers/practitioners, not so much of the official cults as promoted in the cities during the peak years of Imperial power, as to the older, more anciently Roman beliefs. In the neighborhood of Rome that is; presumably elsewhere the local, rooted "pagan" ("pagan"="heathen"=people of the countryside) tradition would be something else--but in no case identical to the urbanized cults that kings and emperors found useful to cultivate.
The thing about properly pagan, indigenous beliefs as adhered to sincerely and stubbornly in the various countrysides was that they were indeed local, and adapted to a peasant way of life; as soon as sophisticated and ambitious urban ruling classes started agglomerating various kinds of empires, be they mercantile confederations like that of Athens or the more usual blocs of military conquests, they found that they needed to modify the cult to span their territories and to address issues that local villages did not need to confront. Philosophers would find the local pieties both crude and inconsistent and would seek higher, "purer" and more sweeping metaphysical answers to the questions religion addresses. The Greeks would try reworking their native myths into a more elaborate system.
(One feature of Christianity that made it a candidate for eventual canonization as the state religion was that early on, its apostles (notably Paul) had sought to harmonize it with Greco-Roman high philosophy, taking the position that Christ had the answers to their conundrums, and doing so in Hellenistic language familiar to Roman citizens like Paul. Presumably the rival cults that were also such candidates were also reshaped in such Hellenistic terms--the tricky bit would be to gratify the philosophers while also retaining mass appeal to the low-class majority.)
As they conquered, the Roman ruling classes were rather restless dabblers in various religious fads. A trademark of their expanding rule under Republic and then Emperors was a broad tolerance and a tendency to equate local deities with their own, which had themselves been reworked for greater consistency with the Greek model. But one feature of religious devotion is that one wants to believe one has arrived at (or been raised in) a true religion; diversity in belief can tend to undermine one's confidence. So the hunt was on to find one broad cult that could strongly dominate everyone on the same terms.
As it happened the cults of Sol Invictus and of Mithra were strongly favored by ranking Romans, particularly soldiers, around the time Constantine cast his decisive vote in favor of Christianity. But there were other contenders--the cult of Isis had its devotees, and both the military cults above suffered from excluding women as potential acolytes, giving Isis (and Christ!) an edge in that female devotees might raise their children, both daughters and sons, in their devotion--the daughters to raise yet another generation no matter what their various husbands believed; the sons to add to the ranks of those whose opinions were deemed to count politically.
So, barring doctrinal mutations that gave women a stronger and more respected role within their cults, the two odds-on favored military cults probably were actually much weaker candidates than they looked; a single state religion that would be seriously imposed and have any chance of winning serious devotion in both city and countryside would have to give some recognition to women. At the same time it would need some sort of martial edge to enable soldiers and administrators in tough times to do their often brutal jobs. It would need to endorse the rule of the Emperor.
Christianity as it happened did not come quite ready-made to meet these specifications; as with other cults, it actually came in various versions, which gave Constantine the opportunity to mix and match, to stitch together a tailor-made version that could be acceptable to most Christians, palatable to many of the non-Christian holdouts, and facilitate his administration. Had some other cult been thus imposed, it would have gone through a similar refashioning.
Now one feature Christianity has demonstrated in the past 2000 years is a scope for syncretism, for adopting practices and even doctrines of other religions and presenting them as seamless parts of itself. This has been a great help in its entering various regions and displacing the local religion, to a significant degree by absorbing selected elements into itself and "baptizing" them into the Christian world-view. Purists of various generations have been horrified to contemplate how much "heathenism" has been adopted as Christian and have from time to time tried to purge the faith of these accretions, but Christianity as we know it is very much characterized by this. That accords well with the old Roman practice of seeking common ground with the local practices of the various places they conquered.
It's my suspicion that on the whole, Christianity won the competition for "suitable Imperial cult" by evolving the most and longest to match the needs of the society it served. If some other cult were to take its place, that one would have needed to evolve in a parallel manner, and would therefore probably be in a position to evolve similarly once the Empire fell in the West and through its fluctuating fortunes in the East.
Or it could be that Constantine and the others involved in establishing Christendom weren't the shrewd geniuses they appear to have been, and he or someone else might have given the nod to a less robust candidate, the enterprise might thus have failed, perhaps leading to an earlier collapse of the Imperial system. If Imperial Rome were not Nicean Christian for instance, but the Goths had meanwhile been won over to Arian Christianity, perhaps when they invaded they'd have an easier time assimilating and being assimilated by the Imperials they conquered, and established an Arian Christendom where OTL they had endless conflict with a populace devoted to orthodoxy as defined by Constantine. Certainly there would have been some Christians among all the other contenders everywhere; it would be odd if not one of them developed some approach to the union of interests of Church and State to render itself a more suitable cult for a pragmatic military regime. Christians of some denomination seem likely to bounce to the top in this sort of free-for-all that would result from the Emperors failing to impose a cult that meets their needs in advance.
Perhaps I misunderstand the nature of Mithras or Sol Invictus in pretty much dismissing them as possible long-term candidates. Perhaps a "marriage" of one of these to Isis, or some other Goddess cult, could do the trick.
But frankly if all versions of Christianity are somehow ruled out, say because a strong orthodox consensus arises among Christians that they really can't be soldiers by any rationalization, the most likely outcome for a future religious landscape I'd guess at would be a new paganism based on the prior faiths of the waves of Germanic, Hunnish, Magyar, Slavic and so forth invaders and locals. The Slavic and Germanic traditions appear to have been branches of the same roots and some sort of syncretism between them (probably involving less compromise than the Romans did in Hellenizing their own pantheon) might develop; later generations of scholars might unearth the Classical philosophers and recognize in their conundrums the same issues that concern them and look for parallel solutions. Since in this timeline the Classical world failed to adopt a working solution, they are back to square one!
By then, one might expect Islam to have offered another answer--except of course that aside from random "butterflies," it seems plain to me that the context in which Muhammed developed Islam was one where a Christian Rome (as the Eastern Empire is called in the Koran--Rum) posed a challenge to the Arab way of life; had Rome failed to Christianize it is not clear that any kind of monotheism would develop in Arabia--this isn't a "butterfly," it's a systematic shift in the basic conditions. Then again aside from powerful monotheistic Christians of the Empire, Muhammed would have been familiar with Jews, with the Ethiopian Christians, and with the more sophisticated philosophical reformulations of Arabian paganism called IIRC "Sabateans" in the Koran, and accorded a "People of the Book" status along with Christians and Jews. So something like Islam arising at Mecca is not impossible perhaps, and then, even assuming that a non-Christian Rome had somehow followed a parallel path thus far and a Justinian-like figure had once again secured control over Egypt, Levant, and North Africa, I'd think the *Muslim Arabs would have even more success, with their monotheistic religion meeting the needs of an Imperium more successfully than the fumbling alternatives hit upon in lieu of orthodox Christianity as we know it. Lacking the stubborn resistance that religious orthodoxy conferred on potential conquests of the Arabs, they might wind up taking the capital in their initial rush, and meanwhile they or their Moorish successors might find Western Europe much easier pickings.