Having the internships obviously helps. Have you just had a look around on jobserve.co.uk? You might find something suitable.
In terms of applying for contracts a lot of it (unfortunately) still goes through recruiters. My advice would be to look at the buzz words in the ad and to change your cv to put all of those at the top. Recruiters see that and think you're the perfect candidate. That will normally get you an interview.
What about having done a few internships? I realise it's not the same but I've at least made some mistakes to learn from already.
I'm starting a job in September, contracting would just be something to fund my personal projects.