Since you have a beta ready, first get a handful of customers pay and get value from your service. This is to iron out any issues that you might not have thought about. Most importantly, it will also validate if your target customers will really pay. Think of this as a dry run. Zero marketing.
Next up, is to take this from handful of customers to say, a bucketful of customers. I am guessing you can do this again, without much trouble, given you know about your target audience. This might be a good time to put up a website and include pricing details.
As to how you should market your service, you don't have to necessarily spend it on ads. You can try to reverse engineer marketing (aka growth hacking). I blogged about it here:http://goo.gl/zVw0Hd).