Given the tough cranial ridge that nature has selected to incorporate into the Klingon forehead, has any non-Klingon given a Klingon an effective headbutt (on their head) on-screen?
Although technically Data is not giving the headbutt but receiving it, only the Klingon Captain Nu'Daq was hurt in the episode TNG: The Chase.
Given the construction of the Klingon head, most species would suffer more harm than they inflict from head butting a Klingon.
There is only one fragile Human who ever accidentally harmed - in a sense - a Klingon with an (accidental) head butt.
DS9 "Let He Who is Without Sin":
WORF: When I was thirteen, I was captain of my school soccer team. We had made the championships, and I was determined to win. Near the end of the second half, with the score tied, my team got a corner kick. The ball sailed up high. Both I and one of my opponents, a human boy named Mikel, leaped up to head the ball. He had position, but I was determined to score. I remember laughing with excitement as I threw myself at him.
DAX: Go on.
WORF: The next thing I knew, the ball was sailing into their goal. I roared with triumph and turned around to Mikel to gloat, only to find him lying on the grass bleeding. Our heads had collided when we both went up for the ball. I had not feel the impact, but I had broken his neck, and he died the next day.
DAX: It was an accident.
WORF: Which only makes it worse. Compared to Klingons, humans are fragile creatures. I realised at that moment to live among them I must practice restraint.
DAX: That must have been difficult for you.
WORF: At first. In time it became part of who I was, who I am.
Since the only way for a fragile Human to hurt a Klingon with a head butt is to make him feel sorry for hurting the Human, and since Worf was probably the one Klingon most likely to feel sorry for hurting people, Mikel was probably the only Human to ever hurt a Klingon with a head butt.
Sisko actually delivers a head butt in DS9: Apocalypse Rising around 27:29, when the DS9 boys attend the Order of the Bat'leth ceremony. There's an establishing shot showing Sisko and a Klingon in a one-handed tugging stance. Then cut to a conversation about blood wine and how it's good the anti-intoxicant is still working "or you would be so drunk you would not be able to stand."
Then cut back to the fight, and Sisko pretty clearly head butts the Klingon before throwing his opponent to the ground. There's a thud sound, Sisko's hair flies in the air, and they're still in the one-handed grip (so not a strike).