I had this problem. iPhone 4s with Sprint. I had just added my gmail account to Mail. After a couple days, I felt like it wasn't necessary, so deleted that account. All the sudden I started getting "cannot get mail. no internet connection available."
I found a solution here:
http://www.apple.com/support/iphone/assistant/mail/#section_4
Click on 'check SMTP settings'
The problem was, that when I deleted my gmail account, it left the gmail server setup, on my phone and it had been turned OFF.
Go to Settings > Mail, Contacts, Calendars. Under Accounts do you see one for iCloud and another for gmail? If so, tap the gmail and look to see if it is turned OFF. I was able to just delete that server from my phone, and it fixed the problem.