If you visit the NHS website you can search for dentists in your area. It should give you contact details, opening times, staff working at the practice as well as whether or not they are accepting new NHS patients. The information may not be completely up to date though, so if you want to know whether they are accepting new patients, your best bet is to give them a ring.
Another option would be to contact your local PCT as they have a list of all the dentists who are contracted to provide NHS treatment and they will know who is and isn't taking on new patients. They should be able to point you in the right direction, or at least get you onto a waiting list for when an NHS place becomes available. Some PCTs can also refer you to a dentist who specialises in treating nervous patients.
In terms of services offered, there are mixed reviews about NHS treatment. Some people like myself have had a mixture of good, bad and indifferent dentists, whilst some have struck gold and found a great dentist who is willing to spend the time and care needed to help them overcome their fear. It completely depends upon the practice and individual dentist. Time can be a big issue though. Because of the way the NHS system works, dentists are under a lot of pressure to see as many patients as possible in order to make the practice financially viable. Therefore if you feel that you need more time or want to take things at a slower pace, then going private may be a better option for you. The materials and treatment provided privately also tend to be of a higher quality than what's available on the NHS.
I was an NHS patient for years because like many people, money is a bit of an issue. However, with a combination of savings, insurance plans and a bit of help from family, I decided to go private as it became obvious that the time, treatment and TLC I needed depended on the dentist I saw and given that my dentist seemed to change every year, I wasn't really getting the continuity or standard of care that I need.
There are a number of options for insurance plans. Many private practices accept Denplan which is a specialist dental insurance scheme that covers the costs of things like checkups, x-rays and basic treatment. It also offers a discount on the cost of more complex treatments. You pay a set amount each month which is determined by your dentist, depending on the health of your teeth. I think it also requires you to be 'dentally fit' before you join. If it turns out that you need a fair bit of treatment, many dentists also allow you to spread the costs over several payments or treatment sessions and some offer interest free credit.
There are also other dental insurance plans such as Boots (I have this - the higher level private plan costs about £20 a month), which pay out set amounts per treatment or procedure up to a maximum amount per year. Whilst they don't cover all the costs, they do go some way towards paying for treatment.
Healthcare cash plans like the ones advertised on TV from SimplyHealth, pay out cash amounts either in full or they pay half of your costs up to a set limit, depending on the level of plan you're on. They also cover other health costs such as opticians, physiotherapy etc. I also have one of these plans from Sovereign Healthcare. For me it costs around £20 a month and pays out 50% of the cost up to a maximum of £140 a year.
It's definitely not too late for your teeth - you would be amazed at what dentists can do these days.

We all know how crippling the fear can be, but you've taken a great step on your journey by posting on here. Once you've had your first appointment, that's the hardest bit done.