http://www.experian.co.uk/
Experian are very reliable for credit record checks. We used them in the bank I used to work for. It looks like your first report is free but last time I ordered one it was £2.
I don't know the answer to your other question, suppose it depends how bad your credit rating is. If you have a reasonable explanation for any bad debts then I would hope they would take that into consideration.
When you get your report you can start resolving any poor ratings by paying off the debts you can and contacting any creditor for those ratings you don't agree with, i.e. if they say you've missed a payment but you can prove you didn't - ask them to update your records, banks have a habit of updating their records but not sending a "feed" through to Experian. So tell them, with confidence, that you wish any amendments to reflect on your credit rating. Also close all loans account and credit card accounts that have a nil balance and you don't think you will need in the future - the less credit available to you the better. Any accounts you feel should be closed once again phone the creditor and explain that it still shows on your credit record as opened and request they take the necessary action to remove it. A loan even with a nil balance impacts your credit rating. Banks are sly as you probably know from recent news reports. But be warned, it will take a couple of months to impact your credit report.
All assuming you are referring to your UK credit record.