What phone? This is relevant because some phones (off-brand Chinese models) have been known to come with dodgy app installers as part of the ROM, in which case you will need to root to remove it.
Otherwise you have got some app installed that is doing this. You may be able to identify it by using something like Addons Detector to check the permissions of your installed apps - anything with the permission to install other apps itself would be a prime suspect. Anything you install from random or dodgy download sites rather than the Play Store is also a suspect.
If you want to just take the "nuke it from orbit" approach, there are two steps: (1) do a factory reset, which will erase anything that's not part of the ROM, and (2) reinstall the OS, which will replace the ROM. The first will get any non-root malware, the second will get any malware that's capable of installing itself to the system. You say you have done the second, but did you do a reset in the process? And did you restore your apps afterwards? If you did you may have restored the one that's behind this.
And don't leave the setting to install apps from third party sources turned on. You can turn it on if you need it, but turn it off again afterwards.
