This is an issue that I run across every time I modify my two-step verification settings in Gmail or set up a new phone. I've asked this question to Google enough times. Now I think I'm qualified to ask it to myself.
If you've set up Gmail as your default Mail app account and you use two-step verification, then Mail won't work if you haven't properly set up your device (and you might not even know it's not working if you're using the Gmail app as your main mail app until you try to share via email something in another app and realize it never gets sent).
There doesn't seem to be a simple user-friendly answer to this problem out there, so after running into this issue and solving it yet again, I figured I'd write out instructions for others to follow.
Best Answer
So you've already set up two-step verification in Gmail...
(If not, now is probably a good time to do so.)
But now that you have 2-step enabled, you can't use your old gmail password to sync your iOS Mail app to Gmail. You will have to sign into Gmail on your phone using a special app password which you can find by signing into Google at your two-step settings page:
https://accounts.google.com/SmsAuthConfig
Then click the "App-specific passwords" tab, and then the "Manage application specific passwords" button.
At this point you may see that you've already set up an app password for your device, but if you've recently reconfigured your two-step settings or activated a new phone, then you'll need to "Revoke" access and set up a new app password.
Set up a new app password for Mail by selecting "Mail" on my "iPhone" (or other iOS device) in the dropdowns and click "Generate".
Next, follow the directions provided by Google:
It's as easy as that.