First of all, I'd suggest looking at "nonetheless" rather than "nevertheless": "never" in this case is being used as an intense negative (it's a somewhat archaic/regional thing nowadays, but survives in "well I never!") instead of as "not ever". Something something Jespersen's cycle.
That said, the oldest attested construction like this seems to be Latin nihilō minus: literally "less" (minus) + "by nothing" (nihilō). The original meaning is something like "not decreased/lessened at all".
This literal meaning is found in Cicero (Pro Milone 19), for example:
minus dolendum fuit rē non perfectā, sed puniendum certe nihilō minus
There should certainly be less grieving, since the action wasn't actually completed—but it deserves to be punished not any less [severely].
In other words, the punishment should not be lesser, just because the crime wasn't actually committed.
It's only a small leap from this to the modern idiom:
But [an incomplete crime] deserves to be punished nonetheless.
Since the English, French, and so on all line up so well with the Latin, I postulate that they're all calques from the Latin. The written record doesn't give much evidence one way or another, but the fact that they all follow the Latin word order is telling.