This answer is thoroughly non original, as it is drawn extensively from Wikipedia's article on the topic. According to this source, Tuscany officially abolished the death penalty in 1786. Of course, this presumably does not count, because Tuscany was later absorbed into Italy, which reinstated it in Tuscany in 1927 under the Fascist regime. So, again according to this article, the nation-state which has officially abolished death penalty for the longest period of time is Venezuela, which abolished it in 1854, so well after Michigan. However, one possible contender would be San Marino, which abolished death penalty "only" in 1865 but which carried out its last execution in 1468.
All in all, if this article is to be trusted, then Michigan seems indeed to be the legal entity which holds the record of de jure abolition, with San Marino by far the record holder for de facto abolition.
Source : http://en.wikipedia.org/wiki/Capital_punishment#Abolitionism