Falco,
I think a large part of your issue is your mind set. If you are new to the business (and even if you are a veteran), you shouldn't just wait for people to contact you on a website. Yes its good to have a lead generation funnel out there as part of your marketing strategy however if you want clients, you have to hit the bricks and go get them.
That means looking at websites for people/companies that fit the niche you want to work with, doing some preliminary analysis, then picking up the phone and calling them to tell them about who you are and why they need your SEO services.
With any new startup and any successful business, sales is a big part of success. If you aren't comfortable with that, hire someone who is or align yourself with someone who is.
Make some goals of calling at least 5-10 businesses in your area to talk about SEO services every day. Once you get known a little and have some successes under your belt you can probably back off the prospecting a little but you should never stop. Alternatively, once you start making a lot of money you can hire someone to do the sales work for you.
Best,
Shawn