Google does offer a $5/month no-ads email service called Google Apps.

According to their homepage, 5 million businesses have chosen that.

http://www.google.com/enterprise/apps/business/

No tracking is trickier, who would believe Google (or any business) if they claimed they didn't track their customers? The lack of ads you can verify for yourself.