Display ads by blog and by category

I'm setting up community news sites at the moment. Every blog on my WPMU site will be a specific county displaying content and ads specific to that county. I also want to make it more targeted and display ads by category on these sites. For example I want to show gardening ads on the gardening posts, financial ads on the finance posts etc.

I know this is a tall order and it doesn't seem any of the existing plugins do this out of the box. Any ideas, suggestions or hacks I could use to get this working? I'm not a strong PHP coder but can hack a plugin pretty comfortably.