Collect email from potential users on a landing page. Then, send them email to let them get to know you and you know them. After a few emails, say 5-7, you could say "hey I have this great product that makes doing X way easier!". A number of potential users who get to say the 5th or 7th email will then trial or purchase your product if you ask them to. That's like getting the first date. Your product ultimately still has to be good for it to be a long term relationship.
Pretty much any email newsletter software worth anything supports some kind of autoresponder series functionality.