Python zlib出力、mysql utf-8テーブルから回復する方法は？

Unicodeはlatin-1と互換性があるように設計されているため、次のことを試してください。

>>> import zlib
>>> u = zlib.compress("test").decode('latin1')
>>> u
u'x\x9c+I-.\x01\x00\x04]\x01\xc1'

そして

>>> zlib.decompress(u.encode('latin1'))
'test'

編集： 修正されたタイプミス、latin-1はユニコードと互換性があるように設計されていません。その逆です。