There was already a Mayor of London: Henry Fitz Ailwyn took office in 1191 and held it until he died 24 years later. King John's charter turned the Mayor into one of the first elected offices in the modern world. Every year a new Mayor would be chosen (by a rather small pool of voters) and every year he would leave the City, travel upriver to the small town of Westminster and swear loyalty to the Crown. The Lord Mayor has made that journey every year for eight centuries, despite plagues and fires and countless wars, and pledged his (or more recently her) loyalty to 34 kings and queens of England.
The Mayor was a power equal to any of John's unruly Barons, and only two months later the first elected Mayor would put his signature to the Magna Carta. He was no doubt responsible for the wording of part 13:
13. The city of London shall enjoy all its ancient liberties and free customs, both by land and by water. We also will and grant that all other cities, boroughs, towns, and ports shall enjoy all their liberties and free customs.
For the next few hundred years, Lord Mayor of London was by far the grandest position that a commoners could reach, and the Mayor's journey was the celebrity spectacle of its day. Over the centuries it grew so splendid and so popular that by the 16th century it was known everywhere as the Lord Mayor's Show. It features in the plays of Shakespeare, the diaries of Pepys and the adventures of James Bond and of course in the pantomime story of Dick Whittington, who really was the Mayor of London three times. In the 20th century the Lord Mayor's Show was the first outside event ever to be broadcast live and it still attracts a TV audience of millions.
The modern Lord Mayor's procession is a direct descendant of that first journey to Westminster. The route and date have changed over the years but the pageantry of Hogarth and Canaletto can still be seen in its lively mixture of London's past, present and future. The state coach is 350 years old, and the pikemen who guard it are almost as old as the Show. Today you will see the City's businesses, Livery Companies, charities, Her Majesty's Forces, the City Police and Londoners from all walks of life come together to enjoy a splendid celebration of the City's ancient power and prosperity, just as they did in the middle ages.
* This didn't entirely work. Less than a year later, when he failed to abide by the terms of the Magna Carta, the struggle between John and his barons become a civil war. Robert Fitzwalter, leader of the rebellious barons, based himself in London and after a series of blunders was forced to seek help from France. Londoners are said to have lined the streets to welcome Prince Louis into the City.