While this is true on a very shallow level, most landlords are happy to rent to "high risk" tenants with increased deposits if you talk to them directly instead of taking your initial rejection at face value.
More and more rentals are being gobbled up my big corporations. Finding someone to talk to who has the authority to make an exception can be nigh impossible.
Eh maybe. I think that largely depends on where you live. Granted, most apartment complexes are falling into that category, but venture out of the city a bit and if you're renting a small 2 bedroom house for $750/mo in Nebraska, it's probably owned by an individual.
Worst case scenario, even in a city, you could sublet or get roommates while you rebuild your credit.