The first step dilemma is a reality. You start at 0 customers, and have to grow. How? People trust you, that other people trust, etc. As a business, you need to network, and word of mouth from people you know can spread in your community since people do know you, and will vouch for your honesty.
But trying to start big without a user base won't work, so you need to grow from the ground up, and the best place is the local community or online community of people who already do trust you, and can vouch for you. It doesn't need to be a corporation to lend trust to you. There is also reviews and authentication of reviews from a third party site, whereby people who use your trust service, can review your service. Just an idea.
Great points:)