Have you worked with social service agencies which specialize in such employment?
In my metropolitan area there is a significant network of employment agencies. Many are faith-based and many work with the homeless and disadvantaged, and it is not unusual for some to cater to ex-cons and felons. They will not advertise this stuff publicly, so you will need to get referrals and inside information on how to find them, but once you hook up with such an agency, your chances should improve drastically. Many of them will counsel you on how to approach applications and interviews, they will broker connections with employers who can overlook such a record, and they really know the communities they work in.
Do not discount the power of your State agencies to help you as well, such as through Vocational Rehab programs.
One drawback I've found to working with these folks is that they're geared to low-income jobs, manual labor, call centers and food service type stuff. They're not well-equipped to handle professionals in industries like IT, but you can certainly help them adapt, and recognize that we're worthy of assistance too. The more professional ex-felons who approach them, the better equipped they will be to serve people like us.
26 years ago, they parked me in a homeless shelter with a newspaper and a public phone to apply for jobs. Not even a typewriter to create a résumé. It was a joke. When I was finally motivated and qualified, I found the right agencies and the right assistance, and it made all the difference in the world.