I've hear an historian mentioning that sometimes after Charlemagne and around AD 1000 the bishop of Rome started calling himself the Vicar of Christ. If I remember my history right, when Latium and central Italy were under the Byzantine rule the Church was also under the Imperial rule (both for political and religious matters?) and the Bishop of Rome was on equal standing with the ones in Byzantyum Antiochia and Jerusalem, but when the Pope and Charlemagne founded the western Empire I suppose the Bishop of Rome managed to detach himself from the Byzantines..?
When (if) that happened, was it something that was established by law, edict, or just a given?
The title of "Vicar of Christ" specifically in reference to the Bishop of Rome was being used as early as the pontificate of Pope Gelasius I (492 - 496 AD) when it apperas in liturgical texts. It is possible that it was being used earlier. The title was used somewhat inconsistently, and became more common as popes began claiming more and more monarchical authority in the high and later middle ages, especially under Pope Innocent III (1198 - 1216 AD), with whom the title has become particularly associated.
Whether the Bishop of Rome was the equal to all of the other bishops goes to the heart of a dispute between Latin and Greek Christians that continues today. Roman Popes have historically claimed a unique teaching authority as successors to St. Peter, traditionally said to have been martyred in Rome and to have enjoyed a unique relationship with the Roman church. Peter stands out among the other Apostles in the four canonical gospels as being The Rock on whom Christ built the church, the one to whom Christ gives the instruction "feed my sheep," and to whom Christ gave the keys to the kingdom. What exactly this meant and to what extent these powers inhered in the successors to Peter's ministry has historically been a subject of debate, with Popes claiming the broadest possible authority, and the eastern churches believing this primacy was more of a primacy of honor.
It is true that for a long time Roman Bishops had to compete for power and influence with Roman Emperors in Constantinople and with the Ecumenical Patriarchs. The popes had to worry about this less and less over the course of the 8th century as the emperors had to worry about more pressing threats from expanding Muslim powers on their borders. The Empire was losing control over Italy and everybody knew it. It is true that the Carolingian Franks enjoyed a special relationship with the Roman church in great measure because they were powerful enough to act as a counterweight against the power of the Lombards, who continually threatened to gobble up the rest of Italy and infringe on the sovereignty of papal territories. The use of the term Vicar of Christ in reference to popes, then, precedes Charlemagne's imperial coronation in 800, though the transfer of imperial power that this act implies is an important historical landmark in the papacy's relationship with the churches and secular rulers in the west.
Readings
Eamon Duffy, Saints and Sinners: A History of the Popes
Karl F. Morrison, Two Kingdoms: Ecclesiology in Carolingian Political Thought
Aloysius Ziegler, "Pope Gelasius I and his Teaching on the Relation of Church and State"
Thomas F. X. Noble, The Republic of St. Peter: The Birth of the Papal State, 680 - 825