You don't need a phone contract to have a phone. I used to have a contract and actually paid a lot more per month than pay as you go, so I exclusively use pay as you go now. Originally I was using a UK SIM card in my unlocked US phone, but that phone died and I bought a new UK phone to use with the same SIM. It was £109 for a samsung smartphone. You definitely don't need a credit check for that!
You'll build up credit over time once you have the bank account and job.