What was the first recorded non-violent toppling of a dictator?
I would go with Cyrus the Great of Persia, and his conquest of the Babylon king Nabonidus in 539 BC. It's often referred to as a bloodless coupe. There were battles initially between the Persians and the Babylonians (Opis); but when Cyrus laid siege to Babylon, the citizens eventually opened their gates to Cyrus and welcomed his army into the city.
The Military 100: A Ranking of the Most Influential Military Leaders of All Time page 42.
In 539 B.C. Cyrus turned his army to the rich kingdom of Babylon, to the east. The babylonians, unhappy with their own leadership and impressed with Cyrus's treatment of previously conquered territories, surrendered without a fight. Included in the bloodless conquest of Babylonia were Palestine and Syria. Cyrus's humane leadership continued. Along with a lack of brutality against the citizens of the newly acquired territories, Cyrus righted several previous wrongs.....
Cyrus the Great Persian King (ca 590-ca 529 b.c.) rank 10
The First Roman I can think of doing it would be 458 BC Lucius Quinctius Cincinnatus The first dictator of Rome.
Appointed Dictator by the Roman Senate when an enemy invaded their territory, He assumed dictatorial powers, defeated the enemy and then laid down his powers and returned to his farm when the danger was over.
In 458 BC, the Aequi to Rome's east broke their treaty of the year before and attempted to retake Tusculum (Frascati). The consuls for the year—L. Minucius Esquilinus Augurinus and G. Nautius Rutilus—led out two armies, one to Tusculum's relief and another to strike against the lands of the Aequi and their Sabine allies. Upon reaching Mount Algidus in the Alban Hills, the army under L. Minucius Esquilinus Augurinus encamped and rested instead of immediately attacking. The Aequi quickly deployed around their position and successfully besieged them, with only five horsemen escaping2 to tell the Roman Senate what had happened. With the army of the second consul unable to help, the senators fell into a panic and authorized the nomination of a dictator. G. Nautius Rutilus or Horatius Pulvillus named Cincinnatus for a term of six months.
A group of senators was sent to Cincinnatus to inform him of his appointment, finding him while he was plowing his farm.[c] He asked them, "Is everything all right?" and they replied that they hoped "it might turn out well for both him and his country", asking that he don his senatorial toga before hearing the Senate's mandate. He then called out to his wife Racilia, telling her to bring his toga from their cottage. Once he was properly dressed, the delegation hailed him as a dictator and ordered him to come to the city. He crossed the Tiber in one of the senate's boats and was greeted on his return by his three sons and most of the senators. Several lictors were given to him for protection and enforcement of his orders.
The next morning, Cincinnatus went to the Forum and named Lucius Tarquitius as his master of the horse.2 He then went to the assembly of the people and ordered every man of military age to appear on the Field of Mars (Campus Martius) by the end of the day with twelve times the normal amount of encamping spikes. They then marched to the relief of the consul's relieving army. At the Battle of Mount Algidus, they used their spikes to quickly besiege the besieging Aequi. Rather than slaughter them between the two Roman camps, Cincinnatus accepted their pleas for mercy and offered an amnesty provided that three principal offenders were executed and Gracchus Cloelius and their other leaders be delivered to him in chains. A "yoke" of three spears was then set up and the Aequi made to pass under it as an act of submission, bowing and admitting their defeat. Cincinnatus then disbanded his army and returned to his farm, abandoning his control a mere fifteen days after it had been granted to him