There are some reports that T-Mobile may provide free G-Mail support for Android phones. This would not require a data plan. I assume it would require a T-Mobile voice plan. It may be sponsored by advertisements, but Gmail users are already used to advertisements.

http://techland.blogs.fortune.cnn.com/2008/09/22/t-mobiles-google-phone-may-offer-free-e-mail/
http://www.androidauthority.com/index.php/2008/09/22/t-mobile-g1-to-offer-free-gmail-email-with-no-data-plan/