Local Paper - VERY Expensive but can be run on a week to week basis.
Local Newsagents - 50p - £1 per week for an advert.
Local Ink Cartridge Place / PC Related Business - ask if they will display your ad and you'll hand out their cards.
Longer Term - Nothing beats Yellow Pages, Thompson, etc
See if you have a Local Listings site on the internet where you can pay a fee to be listed per month.