>How do you cash a paycheck if you are without an address or a bank account?
You simply sign the back and take it to the bank and they will give you cash.
>How do you establish that you are a citizen and are legally able to take a job if you are unable to safely store your documents?
I honestly have no idea.
>How do you get health care, inclusive of mental health care, if you are unable to pay for it?
The answer is to get a job which is an obvious catch 22.
>If you are without a secure residence, how do you know when to wake up, how do you clean up, put on fresh clothing, and get to work?
I think there are a variety of viable answers here ranging from family, church, charity, shelters and gyms that this is a challenge but not insurmountable for a motivated individual.
> If you rely on public transit, how do you reliably get to work?
By using public transit? I don't understand the question.
> How do you establish residence if you have no reasonable credit or references?
This is a huge issue, imo. The only real option is paying in advance but that is obviously much more difficult.
> How do you save your deposit, first month's rent, and last month's rent, if you are unable to even get a bank account?
The answer is cash but the next question is how does a homeless person keep thousands of dollars in cash safe.
I think you've gone out of your way to add solvable problems to your list to make the issue seem insurmountable but you've definitely included two issues which I think are massive and one that's less difficult but also easily solved.
Starting with the solvable problem, banking, add basic banking services to post offices. It makes a lot of sense, imo.
The healthcare problem is a big one and I think the most popular answer to that question would be socialized medicine, which I support, but I'd also be open to hearing other solutions.
The biggest problem, I think, is housing. Not just because of cost but, as you mentioned, credit and rental history are going to be a major problem. Perhaps some sort of temporary (but long term enough to allow a history of payments to be shown, like 12 months or so) housing that could be offered to those in need to get back on their feet. Possibly even a requirement that apartment buildings make a unit available for this kind of renter.