Signatures work on easy boards (ezboards) google crawls that place all the time. You can start an ad campaigne for as little as $100 or you can pay as much as you want.
Got to a screen printing shop and get T-shirts made up. Now find a place in real world that has to do with your sites main topic. Hand out the shirts with you URL on them. People will almost never pass up a free shirt. You can get 100 shirts for $200 or even cheaper in the right places.
Make sure your meta tags best sell your site. People tend to over look these. Google still pulls a site description off the meta tags.
Topsites can do wonders for your site. If you have the bomb ass site and you are on a topsites with many similar sites, you just might steal thier traffic.
Run your own topsites. This will have(when full) 100 links to your site. This will help your site out a ton. Plus you have 100 sites asking thier members to go to your site.
Creat a community on MSN and say we have moved. Put a link to your site. Do the same for Geocities, Tripod, and so on. This leaves you exposed in high traffic areas and some searches might pick it up.
Get major sites to link you if you can. The more busy sites that link to you the higher your rating in Google.
That should keep you busy for a while.
My New site OpenEyes