make yourself additional cards on people that have a clean old credit history, it should help a lot.
That is, get someone with a good credit score to add you as an authorized user on a long held card. They don't even have to give you the card to spend on.
If you can get more than 1, even better.
AMEX requires AUs SS#. That's good for you.
(If you pay a stranger to do this for you, it may be illegal.)