Same with social media accounts. Don't buy followers, but instead just work to continuously build your follower list. Look at your competitors and see who follows them and who they follow. Follow all you can. Post new content and different content to each account.
2. Time - unfortunately you will not see results overnight. Don't get discouraged. Keep at it.
3. Sitemaps - Google/Microsoft Webmaster Tools. Create sitemaps for your product site and blog. Use these tools to track your rankings along with keywords that visitors are using to reach your sites. You will probably find keywords you had never thought of. Target those keywords.
4. Google Adwords/Bing Ads/Facebook Ads - I know you said you didn't have a budget for any ads, but often times you can find ad credits for these networks. Google is infamous for offering spend $25 get $100 credit coupons for new customers. There is probably someone on here that has one they can get you.
5. Look at your competitors and find their weaknesses. For example, I am by no means a SEO expert, and it is not my specialty, however, I worked with a client last year that was looking to rank on the first page of Google for a specific keyword. We found a competitor's blog that was not getting updated often (last update had been over a year earlier). By publishing fresh content, sharing that content, and getting clicks we were able to overtake that competitor on the first page within 1 month.
6. Find "partners" or "cheerleaders". Reach out to sites that are in your market to have them write about your product. Look for reporters who have written about similar products previously. Reach out to them. If you are a good writer, or can afford a couple hundred bucks, you can write your own press release and put it on PRNewswire. While it may not get picked up by any reporters, that site tends to rank well by itself and will draw attention to your company/product.
7. Depending on your product submit it to a site like Product Hunt or do a Show HN.
8. Make sure the underlying code of your website is well written. Make sure the titles are clear, and that you take into account good SEO techniques (use of meta description, heading tags, anchor text, useful content on pages, etc...).
9. Good luck and remember #2 above. If anything the most important thing to remember is that it will not happen overnight, so do not give up easily.