The best way to gain credibility is to write a book. Authors have instant credibility as soon as their book is published. The secret is that many of these books are ghost written with the purpose of promoting the author. You can do the exact same thing and outsource your book about online marketing for local businesses. The best part is that it is easier than ever to self publish a book on Amazon. Then you can tell a potential client that you wrote a book on the subject and give them the link to Amazon. They will never doubt your credibility after that.
Another good way to build your credibility is to do local talk radio shows. Just contact your local radio stations to find out about being booked for a show. Many local shows are constantly looking for local experts to interview. Then afterwards, publish the recording to your website and you have another source of instant credibility.
Next you will want to get logos of different companies and organizations on your website. Start with the national shipping companies, UPS and FedEx and even the USPS. Then put Mastercard and Visa logos or any other payment method you accept. Potential clients will see that you have already been approved by a third party and are trustworthy. Next move on to the local business organizations that you are a member of, such as the Chamber of Commerce or BBB.
Another way to help your credibility is to put a picture of yourself on your website. Also put pictures of you and other important authorities in your area of expertise. It can also help to have pictures of you at a charity event. Then record a video of yourself talking about the services you offer and some specific advice. This will create a personal connection with the potential client.