I believe the reason that the Indian consulate requires proof of valid status to issue you a passport, is because they are trying to prevent people who have naturalized in the U.S., and thus have automatically lost Indian citizenship, from still pretending to be Indian citizens. Having proof of valid non-citizen status proves that you currently (or recently) was not a U.S. citizen. If someone has already naturalized, they (usually) have no proof of status in the U.S. other than their proof of citizenship, which would alert them that you may not actually be an Indian citizen.
Unfortunately, this means that people who are out of status, like you, are stuck. (It's kind of a Catch-22 -- you are illegal, but can't leave because you need a passport to do so, which you can't get because you're illegal.) Basically, I think they need you to provide them some proof that you do not have status, or otherwise is not a U.S. citizen. Unfortunately, there isn't really such a document that you can apply for. I would have thought that the Extension receipt or denial would be sufficient (did you try that?), because it shows that you were recently in a nonimmigrant status, and trying to extend it; and someone who is a citizen, or almost a citizen (permanent resident) would not apply for such a thing.
Maybe you should ask the Indian consulate what is an acceptable proof that you are out of status in the U.S. I have heard that in some such cases, people have gone to the Social Security Administration to get a document that you are not listed as a citizen in the Social Security database (even though this is not a good proof, because you're the one who needs to tell Social Security to update your status when your immigration status changes). If you can get that, you can try that.
I guess in the worst case, you can report yourself to the ICE, and get yourself deported, in which case they will tell the Indian consulate that you are illegal, and work with the Indian consulate to get you a travel document. Though this is kind of an extreme case and if you really go through deportation, you will have consequences, e.g. 10-year ban.
Update: Looking at the BLS page on renewal of Indian passport after it expires, it seems to clearly mention an option for people who are out of status in Documents Requirements:
Notarized Color photocopy of current valid US visa on passport or
Green card or Employment Authorization Card or I- 797 approval notice
documents. Student visa Status holders must enclose I-20 Document as
well. If your visa has expired and/or or you have the receipt notice
for extension of your visa then: NYC, SFO & HOU Jurisdiction
Applicants - must provide a notarized no status affidavit with
photocopy of the valid passport and the green card of two witnesses
duly notarized + 7 Copies of Nationality Verification Form (Given in
Point 2 above) are required and each copy must have an original
photograph affixed on it. WAS/ATL/HOU/CHI Jurisdiction Applicants -
must visit the consulate in person for an interview before applying at
the passport application center.