Brian became immortal because of his contact the aliens.
After a few weeks on the cross without dying, probably with a few more wacky hijinks along the way, Brian unties himself from the cross. Unfortunately for him, this is more proof than ever to his followers that he's the Messiah, but he's still not the Messiah; he just unwittingly got some alien medical thing, which isn't the same thing. An exasperated Brian flees the country and starts Walking the Earth. Centuries later, Brian finds himself in front of a lake, from which the Lady of the Lake emerges and holds aloft Excalibur, signifying by divine providence that Brian, now dubbed Arthur, was to become King of the Britons. Brian has a "Here We Go Again!" moment, but this time, he just gives up and plays along. Then God appears to Brian/Arthur and tasks him to find the Holy Grail, choosing him specifically because he "hates people crawling 'round on their knees and worshipping him" — he thinks Brian might be the only human who could understand how much God hates it. Thus, as you might guess, we get to the events of Monty Python and the Holy Grail.
Brian/Arthur can use his experience from Walking the Earth to his advantage — for instance, this is how he found those coconuts that so puzzled the French knights at the beginning of the film. But he's totally unprepared for the film's ending, an Anachronism Stew caused by a weird Time Portal, similar to what we saw in the "Elizabethan Pornography Smugglers" sketch. This transports the policemen back to where they came from: the 1960s. Except now they have Brian/Arthur with him. Poor Brian/Arthur, trying to reconcile all the silly things he's seen, joins a comedy troupe and adopts the alias Graham Chapman. Except he's slowly going insane, confronted with a world as mad as ever, and most of the characters "Chapman" plays in Monty Python's Flying Circus are actually how Brian/Arthur now sees himself.
Brian is saved by aliens!
After the movie ends, friends of the aliens who were shot down arrive on Earth. They can detect Brian from his earlier encounter with their friends, and they take Brian up into their spaceship. That's how he "ascended" from Earth. The aliens are an hallucination by the construction worker shown right before that scene.
He's clearly stoned. Brian will go to Heaven.
The shot at the end of the credits pans way up into heaven, implying this. Brian was a good person, and didn't deserve any of the crap heaped on him, so God decided to cut him some slack, and give him a nice afterlife. Or Brian just snuck in at the same time His son entered through the Pearly Gates. The Centurion played by John Cleese was Naughtius Maximus.
In other words, he's Brian's father. He's so stunned at being confronted by his bastard son that he forces a laugh and is insistent that nobody like that could possibly exist. The crashed alien space ship wound up buried under Jerusalem...
...and is better known to history as the secret treasure of The Knights Templar. The reason Brian knows so many Jesus quotes when the crowd he's preaching to don't...
...is that most of these quotes are from the Sermon on the Mount. Even though Brian involuntarily missed most of it, he was clearly interested in hearing it, so he got someone else to repeat it for him later. That person was actually one of Jesus' disciples, and insisted on recounting some of Jesus' other teachings, like the Parable of the Talents. The People's Front of Judea is suffering from lead poisoning.
It's from the wine, which the Romans were known to lace with lead, and which at least one person is keen to list as one of the many things that "the Romans have done for us". Before then, they just had kosher wine, which was the butt of jokes in the West for centuries (the actual Israeli wine industry notwithstanding). The Centurion who took issue with Brian's Latin used to be an actual grammar school teacher.
He treats disobedient soldiers, bad students, and political dissidents equally — he makes them write lines with the gentle threat of physical punishment if they try to shirk out of it. He is also the Roman equivalent of a Drill Sergeant Nasty and the absolute terror of his legion.