That is all a major pain in the ass and, as others have pointed out here, those that want to do harm are likely already doing this. I wouldn't expect normal folks to be able to do this, nor should they have to in order to preserve privacy.
Or are you suggesting I should camp out in the airport for a few hours to restore my phone before I can figure out where I'm going and get ahold of my contacts?
Oh let me guess. Your solution so to print those contacts and maps (oh, no GPS to figure out where I am on that map) and use a pay phone (because I still need to re-install the apps I'd normally be using to contact people). Heck, I don't actually have phone numbers for > 90% of my friends. I just have them on Facebook, Line, WhatsApp. The only people I have phone numbers for are for people who've been friends longer than about 15 years, in other words before messaging
It's absolutely possible traveling without a smartphone. I've done it plenty of times before smartphones became a thing. But smartphones make it so much easier.
It's honestly kind of lazy not to take precautions, particularly when it's that easy - you've already listed out exactly what I'd suggest, and it's how people muddled along for decades in the before-times, more or less successfully.
I would suggest learning how to read maps. It's really easy, especially in urban areas. Find the nearest intersection, and look where it is on the map. There you are.
There are plenty of backup tools available on the internet, this isn't really a problem with Android. Personally that's what I do each time I travel abroad. Both because I might loose my phone/laptop and because on can never be sure what software/content is legal(or not) in this or that country.
Some people got jailed abroad for content/software that would be deemed legal in my home country, on their computer.
Name one and describe the process. So far everything I have tried takes hours and often loses a bunch of settings that need to be restored manually. It requires significant amounts of work. Also it seems most tools need a rooted phone
A minor inconvenience given the legal risks. If you don't want to deal with that just get yourself cheap used gear dedicated to travel purposes.
I have used the built in backup to Google and noticed that restore takes many hours and a lot of apps lost data and settings. It took considerable effort to get back to normal. Definitely too much work to spend on my first day of vacation.
A burner phone may work but then you don't have access to all your data.
If you install TWRP recovery (root is only required for the installation, not the maintenance), you can do a full-phone backup.