How do I disinfect my device infected with a malware?

OP here.

So, I was facing this problem, and was surprised that my initial google search didn't turn up anything actually helpful, and multiple harmful things, among the first handful of pages I looked at, and then I found a good answer in google's documentation, here.

Posting here so others can benefit.

Specifically, Google advises there (emphasis mine):

Remove problem apps

1. On an Android phone or tablet, press and hold your device's power button.


2. On your screen, touch and again hold Power off Power. Your device starts in safe mode. You'll see "Safe mode" at the bottom of your screen.


3. One by one, remove recently downloaded apps.
   
   
   
   
   • Tip: To remember the apps that you remove so that you can add them back, make a list.
   
   


4. After each removal, restart your device normally. See whether removing that app solved the problem.


5. After you remove the app that caused the problem, you can add back the other apps that you removed.

(There are more suggestions (2 more big steps) there after those five sub-steps, as well as links more detailed instructions on how to delete and restore apps.)

Additionally, here are some things to skip or avoid - they failed or worse:

• I found that quitting the suspect app and rebooting didn't clear the infection.
  
  My device is not rooted, and I had only installed apps via Google Play.



• Tip: The phone came with Lookout anti-virus installed; (despite point 2, below) it was useful for identifying the recently installed apps. I couldn't find a place where Googled logged that info, but Lookout had a log that showed (confirmed my recollection of) what I'd installed in the past two+ weeks: only one app (and auto-installed updates to many apps).




• I found that one cannot even minimally trust Google Play reviews; specifically, I found that my review of the suspect app appears when I view the app on the infected device in, but does NOT appear when I view the reviews of the app on the web. App: Free VPN Master - Fast secure proxy VPN from Freeemaster2018




• I also cannot trust Google to keep malware supposedly from its own subsidiary - VirusTotal - out of the Google Play store! An official app for running installed APKs thru VirusTotal is described here and was once available thru the link found there (now dead, but in archives), but now there's only a fake copy (here) that's actually malware!




• I find that reporting these issues to Google/attempts to google, including the Google-supplied and Google Ad Policy-violating-ads, to be difficult and fruitless. Google seems to be intentionally avoiding accepting such complaints; submission forms are broken and Google staff I interacted with seem to be trying hard as they can to politely but staunchly refuse to attempt to replicate the bugs. (Reminds me of this story about Apple politely but staunchly refusing to admit the obvious!)

I should note: There are some other (inferior, IMO) answers to much the same question at Unable to remove malware:

1. The best way to remove ~99% of all malware is to simply factory reset the device. (actually in a comment) (IMO, this sledgehammer/nuke from orbit approach is effective, but typically overkill that results in data loss.)


2. A good explanation of WHY anti-virus software for Android generally sucks (when compared to that for PC or Mac platforms.)