We're looking at specifically non-advertising approaches as well. We're playing a little with Google AdWords and will likely try paid ads on /r/fitness - however straight up advertising on /r/fitness like forums is against their rules (and well-moderated, cough* we tried).
Having an established relationship with the moderators and/or being an already respected member of the community helps a great deal in those scenarios. Obviously, that takes a lot of investment in time.