Output Python zlib, come recuperare dalla tabella mysql utf-8?

Unicode è progettato per essere compatibile con latin-1, quindi prova:

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

E poi

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

MODIFICA: Corretto errore di battitura, latin-1 non è progettato per essere compatibile con unicode, è il contrario.