Traversable es, en cierto sentido, la clase de contenedores cuya estructura tiene una "ruta" (que puede corresponder a una lista), cuyos elementos pueden modificarse sin disolver la estructura. Por lo tanto

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)

Sin embargo, ese recorrido de estado de lista parece un poco hack y probablemente no sea la forma más eficiente de hacerlo. Supongo que habría una función estándar que lograra lo anterior o una tarea más general, pero no puedo entender cuál sería.