Android - Unwanted apps auto installing without me doing anything. How to stop them?

The symptoms listed in the question indicate that the malware has infected the ROM (system partition most likely) or it was already shipped with the ROM and now has begun to show its color.

In your particular case, as your hunch proved it to be correct, it appears to be App Center app which was acting as the malware. Disabling it stopped those installations.

If anyone has identified such malware as a system app which cannot be uninstalled, see if you can disable it from GUI. To disable it, go to Settings app → Apps → (three dots line, if exists → Shows System) All apps → your app → Disable.

If the Disable button is greyed out and if you don't have root access, than you can block the app from being run. You would first have to identify the package name of that malware app. You can use an app, such as AppXplore to know the package name. For example, in the screenshot here the package name of the app Android Live Wallpapers is com.android.wallpaper which is listed below the title of the app. You can find so for your malware too.

After that, setup adb in PC, enable usb-debugging and execute the commands:

adb shell pm hide PACKAGE               # for Android Lollipop
adb shell pm uninstall --user 0 PACKAGE # for Android Marshmallow and Nougat. This is bit tricky. Some reports its result positive, while others, negative.
adb shell pm disable-user PACKAGE       # alternative to aforesaid second command for Android 5.0 and above
adb shell pm block PACKAGE              # for Android Kitkat
adb shell reboot

PACKAGE should be substituted by the package name of the malware app.

Know that if you have issues identifying the malware app you may have to try a few things, such as

• monitoring the network using a firewall or a system monitor to single out that app, such as through OS Monitor app, or
• by identifying system apps with signature not matched with your OEM's and Google's and than analyze which amongst the leftovers might be the malware.
• perhaps scanning the phone with some anti-malware tool from Play Store could help as well

• lastly, if the malware app was stupid enough to leave the installer package name as its own package name, than provided you still have at least one of the apps installed automatically (like Clean Master) by that malware, you could do:

  adb shell pm list packages -i PACKAGE
  

This would show some package name next to installer=. If it is null than you got to try something else until you figure out the package name of the malware app.

If you've root access, you can choose to disable or remove the malware app. There are many apps in Play Store, such as Titanium Backup, System App Remover, and the likes which can remove or disable a system app. Use any of them to remove that malware. Be very careful, since removing a system app may make your phone non-bootable and that means, taking a trip to service center of your OEM or getting yours hands more dirty.

At last, if you can install a custom ROM or if you are sure your stock ROM was clean and you have access to it, than by all means, get the device flashed by yourself or those who can do so for you. Running a system already compromised by a malware is a risky business.

And keep the Unknown sources under Settings → Security disabled, to remain on safe side.

If you have root access

1. Select an auto-installed app (any one works)
2. Find its package name (There are many ways to achieve this)
3. Target the file /data/system/packages.xml and open it in a text editor
4. Find the package name in Step 2
5. Scroll the line to the right and look for

<package name="xxx"... installer="xxxxxx">

You may find many occurrences in Step 4. If that line doesn't look like this, go to next match.

6. Take down the content of "installer" and find that app. Get rid of it.