Lots of "paid" marketing avenues that aren't ads. Remember to factor in time and opportunity costs when deciding whether to go for organic style or ads. Most people have time to throw at developing organic content, and it'll pay off over the longer term, however, it isn't "free" when all said and done.
Some "free" ones:
PR would be a good one, track any relevant industry publications, follow #journorequest on Twitter [0], and reach out to journos writing articles about your industry/area and offer comment.
Reach out to some industry blogs, or the blogs of companies in non-competing verticals to write some value-add guest content. Builds a network, and if you find somewhere where you'd be an additive to another brand (e.g. you provide an email helpdesk solution, can write an article for an ESP about best practices for outbound email content etc...)
Make sure you capture interest on your site, landing page, blog email capture, reaching out to cold leads and asking them if they would be interested in hearing more (make sure you're explicit for their permission). Then keep them on a drip email list outlining the problem you solve, how it fits into the industry, some kind of hook relevant to each user, and then an offer to talk them through getting set up, or hear about what blockers they'd have with implementing your solution. Sell after a build up.
None of this is quick, organic acquisition will compound, but don't expect results with free channels straight away.
We started openredis in 2011, and we reached the 1k customers mark a year later. It's a Redis hosting service for EC2, also available as a Heroku add-on. Aside from the fact that the Heroku add-ons program could be considered some sort of marketing, we've never paid a single ad. For us, the key to getting customers was word of mouth. In 2014, at the three year anniversary, I wrote a blog post about how we got started: http://soveran.com/turning-three.html
If I understood right you are asking how to get the users without advertisement...(?) I think most important thing is good and easy-to-use product. People should be able to start using the product as easily as possible. If the product is for example website, the registration and start of use should not be more than 3 clicks away.
Next thing is social visibility (for example Facebook, Twitter, blogs etc.). Especially inside look for product development and new upcoming features give the users something to wait for. Also referral programs (discount or some other benefit for people who get friends and family join to use the product) are proven to be very working concept.
Also one thing to consider is to allow people use the product for free for example for 1 month and after that either automatic or manual contact to continue the usage and start paying.
The whole thing depends a lot what kind of product you are talking about. Applications have their own channels where you can get users from for example app reviews done by some bloggers on the internet.
I think that is absolutely doable but efficiency depends on the product/service. Start a blog, write about the problem you solve and post it to HN, reddit, and other sites but do not spam, make sure you provide value. You either spend money on ads or you spend time on creating content. Just creating the product, putting it online, and waiting for users to come simply will not work.
You can also use previously written blog posts and link to them in comments areas (discussions) when relevant. The more things you have written about, the more appropriate situations you will find yourself in to link to them, as long as you are active and attentive for the right opportunities.
It is certainly possible. I started charging last November and am just passing this threshold without spending any money on marketing at all. This might not work in all cases though. I have a bit of an advantage in that my users are podcasters and they tend to be good promoters with built-in audiences of their own. Also, my service is just naturally viral. The hosts have new guest on their shows all of the time so new people are getting exposed to the product regularly. When they see the ease of use, many of the guests sign up themselves. Not sure how you would recreate this in another domain but hope that helps.
Ask HN: How did you acquire your first 100 users?: https://news.ycombinator.com/item?id=14191161
Ask HN: How did you grow from 100 to 1,000 users?: https://news.ycombinator.com/item?id=14227063