You don't need the actual green card to start working, but you need to wait for your temporary Employment Authorization card (you should also get a temporary Parole card to be able to travel outside the US). Not a lawyer, but I went through this process 5-ish years ago, that's how it was at the time.
You can probably start interviewing without these cards (as long as you disclose your atypical schedule to the employer), but you won't be able to start working.
You can probably start interviewing without these cards (as long as you disclose your atypical schedule to the employer), but you won't be able to start working.