Im not sure how much time you have, but time is definitely needed to construct a strategy for generating backlinks and constructing an SEO strategy.
Or the only other option is to pay contract workers and outsource. Which if you havent tried https://elance.com or https://odesk.com, you may be surprised at how cheap people are willing to do labor for.
However, the ways that I have seen to be most effective are linking to other sites that are already established (send emails to sites that you frequent and ask would they link back to your site), writing useful original content that educates public on sites such has ezines, hub-pages, squidoo, and street articles. Keep in mind that all of these sources should point to your site as a point of reference.
Building smaller blogs through wordpress, blogger, and tumbler that include the keywords your targeting and point to main site will help ranking if updated on a regular basis. (For this I would suggest a autoblog software, this will really help conserve your time and alleviates the daunting task of daily maintenance)
Make sure you use ping sites when blogging as well. (pingomatic)
Press Release Sites are a good way to boost traffic and generate backlinks
Forum activity, social media, and blog commenting are very valuable as well
As far as a directory submission software, I recommend SubmitEaze Directory Submission Software. It’s a little pricey but it’s a beneficial investment, that will pay for it’s self in a week.
I suggest you not to use any software/automated tools for submission or link building because google penguin algorithm is against paid links & automated backlinks. Build natural backlinks by doing manual submission or just outsource it.