SEO, good content marketing, sponsoring blogs and videos (when done tastefully), product placement, engaging with communities, talking about it in HN/ProductHunt/etc.

All those things are acceptable to most people who block ads, IMO.