The official proof would be the registration documents from Companies House.
https://beta.companieshouse.gov.uk/
Others, such as a VAT registration number would be helpful.
You can confirm the companies associated with specific VAT numbers at this location:
http://ec.europa.eu/taxation_customs/vies/
As to not yet having accounts, then yes, you can refer to the date of registration with wiher Companies House or the HMRC.
It would do not harm – and may help your case – to give the contact details of your accountants, or legal representative. Your client could refer to them, to check on your company status, as they are seen as professionals and tend not to distort the truth (though that is sometimes questionable).
Getting on the supplier list of any organisation can present some headaches, but is usually worth it. Good luck