Actually it's not really that hard, but you do have to be diligent with your settings.
First, a nandroid ONLY works if you go from one phone to the EXACT same model phone. That's probably not likely in the case of a loss/theft emergency, so let's forget nandroids for now.
Now define "everything". I'm assuming you want your personal files and data and all your apps and maybe even your home screen configuration?
Here's how you do it ...
Do you backup apps and settings now? Go to settings and search for backup. Unfortunately depending on your phone model and android version, it could be anywhere in system settings, so searching is easier. The one you want is Google Backup. Make sure that's turned on and everything has synced recently. Just a note here, it doesn't backup the actual app. All it does is list the app as installed and once you log into a different device with that Google account, it will download the apps again from the Play store and then restore the app settings. Also keep in mind this is SETTINGS not DATA! If you have any app data you want saved, you'll need to do that individually. Especially vulnerable are games.
Next, make sure all your contacts are Google account contacts. The easiest way to check is to log into your gmail account on a PC and see if they are there. If so, then you're already good to go for contact information. Now make sure your media folders are set to sync with a cloud service. It doesn't matter which it is as long as you've got it set to automatically sync whenever connected to wifi. If you use Google Photos, that'll take care of any pictures or videos you take with your phone. If you save them to folders other than the default you'll have to tell Photos where to find them.
The most troublesome will be SMS/MMS messages and email. These are stored in a protected database in the system folder and not easily accessible. First, let's start with email. Gmail is all good. It's always in the cloud so don't even worry about that. If you have any other email accounts setup, make sure they are IMAP ... never use POP3 on a mobile device. As IMAP they should also exist on the email server and you're good there, too. You just need to know the account setup configuration. Unless you are using a really antiquated or bizarre, non-standard email account, all you most likely need is the email itself and the password to re-setup the account on a new device. If you do have a POP3 account, you'll have to forward the messages you want to keep to a server off the phone. I'd recommend setting up a permanent forward to any POP3 account to your gmail account (or other IMAP account).
With text messages, you can set an app like
SMS Backup & Restore to run scheduled backups of your SMS/MMS messages to the cloud which can then be restored to a different device should you need to.
Finally, your home screen ... use Nova or Apex launchers where you can backup the settings and screens and then copy them to the cloud.
Got all that?
I know it looks like a lot, but it really is your "set it and forget it" plan. The best way to verify you get the setup you want is to do all that stuff above and then after a few days take a spare phone and try and restore it.
