I don't know about other locations, but in NYC, if you have been FIRED for several years, you are likely screwed. Landlords will want tax returns, W2, pay stubs, and a credit report. If you have been FIRED > 1 year what do you show? All of the employment and tax items will be too old! And if you offer to prepay rent or give them cash upfront you will simply seem shady. The rental market in NYC is so hot, landlords don't need to bother with any 'unusual' situations. They just go to the next 'normal' applicant.
The only solution that might work in NYC would be a second person guarantee.
Ironically, an unemployed person or a recent graduate has an easier time getting a rental in NYC - because they will be working soon.