I have been doing seo fulltime since 1997 and local for about 3 years. I do local in the "traditional sense" and a few other ways I have devised that does not require direct contact.
However, if you are trying to start a local offline business and want to do it in a traditional sense ( find a client, make a proposal, negotiate a fee and implement the work) I would consider the following.
I have only done 2 things in my adult life, real estate and seo/internet marketing. I see a parallel in these two fields on how to start getting clients.
When I was in real estate the people that were ALWAYS the most successful where the ones that had the guts to knock on doors and make cold calls. The guys who spent their time stuffing envelopes, sending postcards and doing everthing else they could to avoid direct contact never lasted.
I acknowledge there are some ways to do crafty mailings, send emails or employ lead generating software. This is all good, but I would not discount direct contact.
Assumming you have acquired basic seo skills and have some sort of web presence, why not do something that most of your competion is not doing and bite the bullet and make those calls or knock on doors.
Once you gain some momentum you will not have to do this for very long. Big SEO firms have salespeople, thier staff is usually 5-1 sales people. This is because face to face selling in this industry is where the money is at.
This may not be what some people want to hear but I believe its sound advice. If I was going to do local seo in the traditional sense and had to start all over again thats what I would do.