In NY state you need to provide either SSN or 6 credit points (the doc that prove you are going to stay in the US for quite a long time and thus you need a driver's license) + a letter from SSA stating that you are not eligible for SSN. Then you can take the written test and get a permit. For road test, you need to take classes in order to get a certificate/receipt, use the serial number on the receipt to schedule road test.