If he had the right to work in the U.S. but did not have a SSN he should have applied for an individual taxpayer identification number (ITIN) from the IRS to use until such time as he obtained the SSN. The employer should not have had him start work without either the SSN or the ITIN. Did he get the ITIN?
As for proving he was employed, for what purpose does he need to prove that?

