If you have a good user base that would be interested in what the other business is offering then the percentage of purchase (CPA) option that they suggested could work the best.
This basically means if users of your website go to their website and buy something you get part of the sale. The only issue comes if they are not being honest in tracking, ask if they are using a 3rd party to handle the tracking, such as CJ.com, LinkShare.com, or others like that.
If your not sure that the ad will attract a lot of your users, then you might want to ask for an upfront fee, if you are using AdSense currently take a look and see how much revenue you make per user, then factor in a growth of at least 1/3 over the next year and give a pricing based on the projected possible loss in AdSense revenue if users where clicking on this ad rather then on the AdSense.
If you don't have AdSense and don't know if your users will like the offer from other other business, then try and simply price on a monthly basis and watch what happens. If your users like it and you see they are using the ad often, you might want to renegotiate the following month, but if your users don't like it you are able to remove the banner the following month. As for a pricing point, its hard to give a arbitrary price, but I go with give a price based on what you can do with the money. If selling the ad space for 1 month at $200 buys you those shoes you've been eyeing then $200 is a good price, it all depends on what you feel your time and website is worth.