By far the earliest match for "punch a gift horse" in Google Books search results is from a 1972 issue of National Lampoon, a U.S. satirical magazine that grew out of The Harvard Lampoon, a satirical university student publication. Here is the snippet result that Google Books reports:
NEVER PUNCH A GIFT HORSE IN THE MOUTH OR SHIPS THAT GO BUMP IN THE NIGHT OR GAGA BABRUUUU FREEZIP BLESH DEEDEEDEE GEMP ... SOMETHING LIKE THAT .
Unfortunately, the snippet window that Google Books provides for this excerpt doesn't show any text at all. Still, given even the very limited context in which the phrase appears, it seems clear that this instance is an intentionally garbled play on the much older "never [or do not] look a gift horse in the mouth," which Christine Ammer, American Heritage Dictionary of Idioms, second edition (2013), says reached English around the year 1500:
look a gift horse in the mouth Be critical of something received at no cost. For example, Dad's old car is full of dents, but we shouldn't look a gift horse in the mouth. This term, generally expressed as a cautionary proverb (Don't look a gift horse in the mouth), has been traced to the writings of the 4th-century cleric St. Jerome, and has appeared in English since about 1500. It alludes to determining the age of a horse by looking at its teeth.
In the National Lampoon excerpt, the author leads with "never punch a gift horse in the mouth," garbling the proverb with a common descriptive phrase ("punch [someone] in the mouth"), then mashes together two unrelated idiomatic phrases ("ships passing in the night" and "things that go bump in the night") as "ships that go bump in the night," and then descends into complete incoherence ("gaga babruuuu," etc.). Ha ha.
The next-earliest instance I've been able to find is from an Elephind newspaper database search, which yields this instance from "Without Leonard, the Spotlight Shines Marvelously on Hagler," in the Columbia [Missouri] Missourian (February 8, 1983):
[Marvin] Hagler [at the time the undisputed middleweight boxing champion of the world] was as bleak as the Cape Cod weather last week. It's not as though he would punch a gift horse in the mouth. He just looks that way with his shaved head and goatee.
The Missourian is the student newspaper of the University of Missouri School of Journalism, one of the most highly regarded Journalism programs in the United States.
The expression next reappears as an "honorable mention" entry in the results of "New York Magazine Competition Number 709" in New York Magazine (January 19, 1991), "in which you were asked for Near Misses. Titles, names, phrases, and the like":
Don't punch a gift horse in the mouth.
[submitted by] H. R. Schiffman, Highland Park, N.J.
It is possible that these two and all or most subsequent instances of "don't punch a gift horse in the mouth" ultimately derive from people exposed to the 1972 magazine occurrence. A considerable number of college- and high-school-age young people did read National Lampoon back in the day. More likely, though, the periodic recurrences of the expression during the last three decades of the twentieth century are instances of absurdist minds thinking alike.