With regard to the question about how cliches are first created, the first thing that popped into my head when I read this question was "Coin a phrase". This article even cites The Bard of Avon in several places. I fully expected someone else had already answered with it.
This paragraph seems to capture the idea of newly created phrases or words nicely:
From there, the verb “to coin” started to refer to anything that was made into something new. By the sixteenth century, coining new words became quite popular, though it wasn’t always considered a positive, innovative thing. In 1589, George Puttenham wrote in The Arte of English Poesie: “Young schollers not halfe well studied… will seeme to coigne fine wordes out of the Latin.”
Regarding the word cliché:
Printing presses gave us the word “cliché,” which comes from the French word cliquer, which referred to the clicking sound made by the stamps on the metal typefaces during printing. How did this come to mean “a phrase or opinion that is overused and betrays a lack of original thought?” Printer’s used “cliché” as jargon for “stereotype block.” From there, the evolution of the meaning of the word followed closely with “stereotype,” the latter of which was originally a “method of printing from a plate,” from the French “stéréotype” in the eighteenth century. By the mid-nineteenth century, this had come to mean “image perpetuated without change.” This further morphed by the early twentieth century to mean as it does today.
