FROM THE NEW YORK DMV WEBSITE:
Note 1: If you are not eligible for a Social Security Card, you must provide a letter or form SSA-L676 from the US Social Security Administration (SSA) that states that you are not eligible.
BUT YOU ARE ELIGIBLE... you would be lying by presenting that letter, you are NOW eligible... go get your SSN (which you will need to start working also).