You could always do SEM (buying facebook/google ads) but the conversion rate / impression is horrible. You'll end up spending a s*** ton for very few leads on your website.
A good branding and word of mouth is generally the best way to advertise.
True, I've tried paying for FB once but never again. It didn't really help all that much, and was not worth it.
You could always try to make flyers and deal them out on nearby subway station
I have thought about that
It's actually not a bad idea. Is that something you did for your server?