IMHO a POD with Julian the Apostate would be too late - a POD that prevents the reign of Constantine would work much better, as Christianity was less unified and the non-Christian religious movements were still stronger and more diverse.
The problem is that Constantine is probably too
early. Without the influence of Constantine, Christianity is unlikely to assert much pull over the socio-political landscape of the west to begin with. It'll probably survive, in some form, but it's far more likely to follow a trajectory similar to OTL's Judaism than OTL's Buddhism.
I think you can have a realistic chance of dislodging Christianity from its dominant position in Rome (and, later, Europe) up until the Battle of the Frigidus in 394. Until that point, there was enough heterodoxy within Christianity itself, and a large enough percentage of Roman aristocracy clung to paganism, that the pendulum could have swung back the other way. After Theodosius takes a hard line against pagans, though, it's all over bar the shouting.
That said, Julian is going to be problematic. He'd need to have a long enough reign to reverse the trends in place since Constantine's time, and his military adventurism makes it a bit tricky to keep him going that long. After he goes, in addition, he'd need someone to continue his policies. It's possible: Julian's not "too late," chronologically speaking, but he's going to have to make some radically different choices than he did in OTL.
I think a more plausible POD is to prevent Licinius from renegging on the Edict of Milan. Without the renewed persecutions, Constantine is more likely to continue hedging his bets, at least publically (with Sol Invictus showing up on some coins, Christ on others), and there's a decreased likelihood of the two emperors coming to blows. Getting rid of Constantine entirely prevents Christianity from reaching critical mass (so to speak...) to begin with; getting rid of him too late makes it that much harder to reverse the trend.
The other possibility is that Constantine's heirs lose the purple to a more pagan-friendly dynasty. This is certainly possible, and there's probably a number of potential emperors available, but the sources are spotty enough that its hard to speak in specific terms.