I really like Google's 2-factor authentication and per-device passwords. The only password stored on my phone is a per-device password for GMail. If they steal my phone, they cannot use that to break into my GMail account. If they steal my real GMail password (keylogger or something), they also need to steal my phone to have the 2nd-factor to login to GMail.
Sure, it isn't perfect, but it's better than without.