Traversable é, de certo modo, a classe de contêineres cuja estrutura possui um "caminho" (que pode corresponder a uma lista), os elementos nos quais podem ser modificados sem dissolver a estrutura. Conseqüentemente

zipTrav :: Traversable t => t a -> [b] -> Maybe (t (a,b))
zipTrav = evalStateT . traverse zp
 where zp a = do
           bs <- get
           case bs of
              [] -> lift Nothing
              (b:bs') -> put bs' >> return (a,b)

No entanto, essa travessia de estado de lista parece um pouco imprudente e provavelmente não é a maneira mais eficiente de fazê-lo. Suponho que haveria uma função padrão que realizasse a tarefa acima ou mais geral, mas não consigo descobrir o que seria.