Are there any services hosting Bitcoin-related ads for websites?
There is not anything like adsense yet, but there are smaller ad platform. Here are a few:


http://dailybitcoins.org/ they offer both ads by number of impression and per click.
http://www.bitcoinadvertisers.com/ they claim to be the biggest, I do not know how true that is.
http://anonymousads.com/ They have a significant presence in the Bitcoin community.
http://puppytwist.com/ they are pretty simple to get started with, high payout too