Given how long it took for monotheistic faiths to become dominant and the methods many of them had to indulge in to become so, I'd argue its not inevitable at all.
The mere fact that Constantine himself mainly converted to Christianity in order to give the empire a single stable religious focus was probably a political decision just as much as one borne out of faith: he could see what had happened very recently during the persecutions of Diocletian: it only strengthened the resolve of Christians who became more fervent and just created more religious unrest. By 324 it had become the empire's majority religion partly as a result of the very persecutions designed to eradicate it. If Diocletian and Galentius had not pursued their purge with such fervour it might have been less of a rallying cry for Christians. Then there was the case of Julian the Apostate: the only reason, IMO, that he had little to no success in restoring more traditional religion is that his reign was so short. Given twenty or thirty years instead of two he may have become a major champion of the older ways and in some respects slowed or reversed the religious changes taking place.
Or even more simply? Nip Gentile Christianity in the bud entirely by, for example, Paul of Tarsus not existing or not converting.