O governo mexicano indica que os viajantes precisam de um "passaporte ou identificação válida e viagens válidas sob o direito internacional ”. Se você não puder obter um passaporte, isso deixará principalmente o documento de viagem da Convenção de 1954 e o Documento de viagem para refugiados . Nos EUA, você pode obter o segundo do Departamento de Segurança Interna , mas não o primeiro (ver comentário).
Os EUA também emitem algo chamado permissão de reentrada mas, até onde eu sei, é Apenas alguns documentos ad hoc que permitiriam à pessoa reingressar nos EUA, pode não ser “válida sob a lei internacional” no que diz respeito ao México. Ainda assim, Wikipedia e USCIS sugerem que ele é de fato aceito como documento de viagem por muitos países para que possa ser outra solução. Se isso não funcionar, outra solução poderia ser conseguir uma permissão de reentrada nos EUA (para o retorno aos EUA) e alguma forma de “laissez-passer” das autoridades mexicanas (não faz ideia se eles emitem algo assim ou quanto custa, mas alguns países fazem).
Tanto o documento de viagem do refugiado quanto a permissão de reentrada são listados como documento de viagem compatível com WHTI pelas principais companhias aéreas dos EUA, como Unidos e Delta então voar não deve ser um problema, desde que você tenha o direito de entrar no México.
Nada disto é particularmente barato ou fácil, sendo um refugiado tipicamente uma droga. Considerando que este é um caso bastante atípico, eu tentaria verificar tudo (incluindo uma exigência de visto potencial apesar do green card) com as autoridades mexicanas o mais rápido possível.