1 and 2 I did; I emailed all the major video game blogs and news sites with a sort of "friendly press release" in which I pointed out the features of my service that would make great attention-grabbing headlines and really appeal to video game players. Only one, relatively small, game news site actually posted about it, and they only did because a friend of mine is an editor there and he specifically told them to.

3: There's a Facebook "like" button and a Google "+1" button on every game's page, and there's a general "+1" button for the entire site.

4 I should look into. A few of my most well-connected users have evangelized about the service quite a bit without any incentives (although they probably understand that the more users and ratings are in the service the better the recommendations will be). So I don't know how much more effective incentivizing evangelism will be; it might be what finally cracks the big game forums as users post their referral links there, but most of those forums forbid referral links in the same breath that they forbid talking about your own service. So, it might get some people banned from their favorite forums, but it would get me a few more users in the process. :\