For Non availability of birth certificate one would still be required to visit the municipal corporation of the place one was born. I am talking about India where the databases are still not connected. You would come across agents who can make an affidavit for you and sell it as Non availability of birth certificate (there is no fixed format for the certificate varies from one region to another), so just be cautious.
Your case since you do not have a birth certificate, you can go with either option.
In case you have time, go in for a birth certificate else if time is a premium go with the option which takes less time.