Yes you can. I had my number before my first paycheck, but if you dont, I believe you would be paid and no NI would be withheld and then when you got your NI number, it would all be taken out in your next check after your supplied the number. (I THINK) You can call the NI office and ask them, I am sure.
However, if you were offered that job on Friday and started the following Monday, you probably wouldnt be paid until the end of November anyway or maybe even December (if you are paid monthly) and may well have it by then.