To coin a phrase is to use a new or rarely-heard phrase in a speech or article in such a way that it rapidly becomes a meme or cliché. The phrase is itself somewhat clichéd and formulaic, although its use in formal writing is still considered acceptable.
A considerable Tory thinker, he will be remembered for coining the
phrase "elective dictatorship" in criticism of the Labour government of
James Callaghan.
― Obituary for Lord Hailsham, The Guardian, October 15, 2001
The phrase may also be used parenthetically after a cliché; in this case, it is intended as a semi-apology. This form is also heard in spoken English.
Markets are prone to irrational exuberance, to coin a phrase, and have
always been so.
― Cents and sensibility, The Times, August 20,
2005
The etymology of this expression is not immediately apparent. The verb "to coin",
meaning "to stamp out of a sheet of metal", dates back to the fourteenth
century. The first known use of the verb in relation to language can be found in a
side note entitled "Cacozelia, or Fonde affectation" from the 1589 text
"The Arte of English Poesie" (published anonymously, but usually attributed to
George Puttenham):
Ye haue another intollerable ill maner of speach, which by the Greekes
originall we may call fonde affectation and is when we affect new
words and phrases other then the good speakers and writers in any language,
or then custome hath allowed, & is the common fault of young schollers
not halfe well studied before they come from the Vniuersitie or schooles,
and when they come to their friends, or happen to get some benefice or other
promotion in their countreys, will seeme to coigne fine wordes out
of the Latin, and to vse new fangled speaches, thereby to shew
thenselues among the ignorant the better learned.
― Project Gutenberg's The Arte of English Poesie, by George Puttenham
The expression is clearly used in a pejorative sense. Likely the author was trying to convey connotations of new language originating as a crude mechanical process rather than as an art. However, the irony of including such a note under the heading Cacozelia was no doubt intentional.
The full phrase seems to have appeared sometime in the 1940s, where it was used in a wry, self-mocking way. It is possible that "to coin a phrase" began as an in-joke; either way, the original perpetrators were almost certainly familiar with Puttenham's work.
Sadly, exactly who coined the phrase "to coin a phrase" remains unknown.