Google's GMail service has been opened up to the public after being invitation-only since its inception.  The only catch is that you must have a cell phone.  Considering that everyone and a grandma has a cell phone these days, that shouldn't be too much of a problem:

The mobile phone requirement was designed to prevent Gmail accounts from being created by robots and stop spammers from signing up multiple times. Google will send an invitation code via SMS, which can then be used to register with Gmail. Only one account may be created per phone number.