The verb phrase 'named and shamed' appears in print at least as early as around 1556, in a marginal note in The Copye of a Letter, Sent by John Bradforth.... (see the sixth paragraph preceding A tragicall blast of the Papisticall trompette and associated marginal note). The context of the note is this:
Peraduenture some will be offended because I speake so plaine. GOD is my witnesse I cannot for very shame name such, as I cold & haue heard Spaniards name with shame enough, ....
The note reads as follows (in part):
But take hede with this warning, or els ye wil shortly be named and shamed.
The collocation of 'name' and 'shame' had appeared in print previously in at least two works. Sometime around 1483, it appeared twice in a work by John Gower titled Confessio Amantis, once in Book 5,
The thyrde whiche was after shamed
Was Nabogo donoser named
and again in Book 7,
That in her lyf she were shamed
And I therof were euyl named....
The collocation appears again in John Skelton's Why Come Ye Nat to Courte, printed around 1545:
No shame to do amys
And yet he is a shamed
To be shamfully named
Early collocations, and use of the phrase itself, are unsurprising; the conceptual association suggests itself after the rhyme is noticed.
In the centuries and decades intervening between the use of 'name and shame' in 1556, and a noticable uptick in such use in the 1990s, the phrase appears infrequently. When it does appear, it is often associated with politics and politicians.
In the mid-1990s, an uptick in use of the phrase is associated with the political rhetoric of the US right-wing senator and presidential contender, Robert Dole, who attacked what he termed the "mainstreaming of deviancy" in Hollywood. As quoted in the Journal and Courier, Lafayette, Indiana, 01 Jun 1995 (paywalled), Senator Dole condemned what he considered immoral Hollywood producers:
Those who cultivate moral confusion for profit should understand this: We will name names and shame them as they deserve to be shamed.
By October of 1996, Home Secretary Michael Howard of the UK had adapted Dole's rhetoric for use in a "law-and-order offensive" that accompanied "his US-style crime bill". One initiative in the Howard crime bill was a scheme
to "name and shame" juvenile offenders....
The Guardian, London, England, 09 Oct 1996 (paywalled).