What travel document can a U.S. green card holder (with no passport, and no ability to get a passport, such as a refugee) use to enter Mexico via air, and then re-enter the United States? How long would it take to acquire, and how much would it cost?
Visa typically go in (or are used in conjunction with) a travel document (that's actually an explicit requirement in countries I am familiar with, I don't know Mexican law but official websites suggest it's the same there, see below). So even if you somehow got a visa, that wouldn't solve the passport problem. But having a green card should exempt you from any Mexican visa requirement so at least the visa should not be an issue, the travel document is.
The Mexican governement indicates that travelers require a “Passport or valid identification and travel that is valid under international law”. If you can't get a passport, that would mainly leave the 1954 Convention travel document and the Refugee travel document. In the US, you can get the latter from the Department of Homeland Security but not the former (see comment).
The US also issues something called a Re-entry permit but as far as I can tell, it's just some ad hoc document that would allow the person to reenter the US, it might not be “valid under international law” as far as Mexico is concerned. Still, Wikipedia and USCIS suggest that it is in fact accepted as a travel document by many countries so it could be another solution. If that does not work, yet another solution could be to get a US Re-entry permit (for the return to the US) and some form of “laissez-passer” from the Mexican authorities (no idea if they issue something like that or how much it costs but some countries do).
Both the refugee travel document and the re-entry permit are listed as WHTI-compliant travel document by major US airlines like United and Delta so flying should be no problem, provided you have the right to enter Mexico.
None of this is particularly cheap or easy, being a refugee typically sucks. Considering that this is a pretty atypical case, I would try to check everything (including a potential visa requirement in spite of the green card) with the Mexican authorities as soon as possible.