There are two totally separate certification issues here.
ONE:
Electrical work done in the UK should comply with the Wiring Regulations, aka BS 7671. But it doesn't have to, legally, the regulations are not mandatory. Part of complying though is the issuing of a certificate showing compliance. For new work there are 2 types, an Electrical Installation Certificate (EIC) and a Minor Electrical Installation Works Certificate (MEIWC, but often shortened to MWC - minor works certificate). For the work you described, an EIC is the appropriate one. Legally, anybody may do any electrical work, and issue BS 7671 certificates - there are no legal requirements for any qualifications, or to be a member if NICEIC, NAPIT etc. So the guy you used is legally allowed to issue an EIC and by the sounds of it he is "morally" entitled to, i.e. he is genuinely competent to do so, and would not be lying when signing this declaration:
I being the person responsible for the design, construction, inspection & testing of the electrical installation (as indicated by my signature below), particulars of which are described above, having exercised reasonable skill and care when carrying out the design, construction, inspection & testing hereby CERTIFY that the said work for which I have been responsible is to the best of my knowledge and belief in accordance with BS 7671:2008, amended to 2015 except for the departures, if any, detailed as follows:
The important thing to note is that he knew all along that he should issue an EIC, and unless he is a rip-off merchant who also knew all along that he was going to rip you off he should not be charging you anything for the EIC - it should be automatic - if he is complying with the Wiring Regulations issuing a certificate is not an optional extra.
TWO:
Electrical work done in the England, Wales & Scotland
must comply with the Building Regulations - there are differences between the 3 jurisdictions, but in Norfolk this is what the law makes compulsory:
Again, there's no compulsion to comply with the Wiring Regulations, but in practical terms it's very difficult to prove compliance with P1 by any other route. But by the sounds of it the guy would have had no problem complying (apart from so far not having given you the EIC).
Some electrical work is notifiable, i.e. you have to either apply for Building Regulations approval before starting, tell LABC how compliance with P1 will be achieved, and then do it that way, OR the work has to be done by someone who is allowed to self certify compliance with the Building Regulations and notify the work after the event. The guy you used cannot do the latter, and it is membership of one of the Competent Person schemes run by NICEIC, NAPIT etc that he was talking about when he said he doesn't do enough work to justify the cost of that. Which is fair enough.
What's not fair enough, BTW, is him getting a mate who is registered with one of the schemes to lie for him - it's a criminal offence and against the terms of membership of the scheme his mate is in. I'd strongly advise that you have nothing to do with any such arrangement.
As the work wasn't done by a self-certifying electrician it should have been notified in advance, and it's not clear that you actually did do that.
Firstly the LABC officer asked me if an electrician was doing the work. Nothing else ! I told him yes.
Did he by any chance ask if you were going to use a
registered electrician?
If so, then that's not what you've done, and you've now got some negotiation to do with LABC, as they will probably say that they would have charged you more had they known that you weren't going to use a registered one.
If not then you've done what you said you would, and more importantly you've done what they OK'd when they gave you permission, so they should not now be quibbling.
But either way you need to get an EIC from the electrician and you should not have to pay a penny for it.