Why don't you just use something like adsense/ypn/adbrite? They don't require you to sell anything, which pretty much does all the work for you.
I'm in the same boat as you my friend, a couple paid directories and a new link cloud site all PR0 with zero traffic and no free links...its taking time and patience but I'm slowly getting links and traffic based on site promotion and link building.
As a potential purchaser I have two questions -- what is your URL and where is the traffic coming from?
As a result of your posts I'll definitely look into selling ad space. I think I will approach potential advertisers directly, there is a chance that the term PR will mean nothing to them anyway. Like you said, it's the traffic they're after. Thank you all for your interest but my website sits in a relatively specific niche so I doubt my site would appeal to you. I am using Adsense and will continue to do so, I just need to explore other ways to monetize my site.