If you aim at selling something that is not limited by geography, there are still many characteristics of your potential customers you can investigate and set as target parameters. For instance, it can be age, gender, occupation, interests etc. I mean that geographic location is only one dimension of targeting, and if you're missing this one, then the target audience is shaped by other dimensions, which should be investigated.
As the local targeting is a huge source of direct traffic, you might investigate different possibilities for referral traffic prior to focusing on advertising. For instance, check out all possible niche forums, blogs, directories, interest groups, Q&A sites (or those from related niches) where you can share information about your product and explain why is it relevant to customer's needs.
You may also test social media strategy for your service promotion: join some Facebook groups and discussions, make a contribution, discuss, ask for opinions, do promotion etc. See how your own Facebook page will do, share visuals, videos and informative content for your subscribers, test different social platforms - sometimes one is more compatible with a specific service than another.
As you've already mentioned, paid advertising is definitely a way to go, but PPC only brings short term results, while promoting your service via different relevant social platforms for attracting referral traffic will sooner or later result in improvement of brand awareness and increasing organic traffic respectively. So, it may be helpful to investigate free opportunities for referral traffic and to research niches related to yours, and may be you'll eventually find out some free opportunities for self-promotion.