 According to the diaries of Michael Palin (qv) a possible title  was "Brian Of Nazareth", which was strongly favored by Palin,  Graham Chapman (qv) and Eric Idle (qv). In the end this was  never used, perhaps to avoid title comparisons with  _"Jesus of Nazareth" (1977) (mini)_ (qv).