Should I alter my pricing structure so that I can offer discounts?

A very good idea, Teasers are a good source of premium conversions and show a glimpse into what the free users might be missing. Be carefull though on, choosing the services to that. Pick something that the users once got introduced cannot go back to using the free one and are glued to it. If the same user is coming back for more of these teasers then you have a grand success.

Advertising paying for itself.

It is hard to say for sure with out knowing all of the specifics of your service or who/what it competes with. However, you have to be careful with a charge twice model. Many customers feel like if they are paying a subscription fee they shouldn't be having to pay a per-use fee.

Per-Use Fee Only

In your example of eBay, there is no subscription fee so they have their pricing structure setup such that the per-use fee is high enough that they can afford to give discounts on that. This has some roots in what the service actually is. eBay doesn't have any direct cost per purchase being made, as in there is nothing physical they are having to pay for in order for that single transaction to be made. So there really isn't any money out of their pocket by offering deals like that.

Monthly Fee plus material charges

On the other hand a twice pay structure may work for you, I will use FreshBooks as an example. They have a monthly fee based off of how many employees and clients you plan on using. They then have fees to send out paper invoices to clients. This fee is considered acceptable by most people because of a couple reasons. First it is actually directly costing FreshBooks money to print and mail the invoice. Second it is something that is not required in order to use the service. What I mean by this is that someone could pay their monthly fee and send out electronic invoices all day long and never have the need to pay for the extra service.

Monthly Fee plus Per-Use Fee

There is one more situation that you could fall under, that being an "exclusive access" type model. I tried to think of a website to give as an example, but none come to mind. What I can use is an exclusive club. Many clubs charge a cover (like your monthly fee) and then charge per drink (like your per-use fee). This works for many clubs that have the feel of exclusiveness. This is usually not the best approach to take when you are first starting up as you limit the audience that you can market to.

Summary

Overall I would recommend you evaluate who your competition would be and look to see how their pricing structure is setup. If you don't have any direct competition to compare against then do some asking around among people who could potentially use your service as to what they would be fine with paying.

I think it's a good idea. It takes advantage of a psychological effect called "anchoring" that is used extensively in marketing. Retail stores use this all the time when they display the retail price with a line through it and their "low" price. It's also commonly used in infomercials. They introduce the product and ask, "How much would you pay?" They give you a fake price and then lower it several times. Finally, at the very end they double the order. Our brains inescapably compare the final price to the initial one and we feel like we're getting a great deal because of it.