Its far easier to convert people who are willing/looking for SEO services than ones that you need to sell it to.
Get a good track record with SEO. Get good results for clients.
Initially you might need to charge less, but when your portfolio speaks of results, then good things will come.
You will have amazing success when you can prove your capability, otherwise you are like many SEO companies who over promise and under deliver.
I see many companies offering incetive bonus for results, you can try hook a client and if you reach target, then he pays you the bonus :)