Welcome to Android Central! After the factory reset and the Setup Wizard, did you go directly to the Play Store to stop any app that might be installing automatically? Try to do that, in case it's automatically reinstalling the culprit app.
If you've confirmed that no other app has automatically reinstalled, then you probably have malware that has installed itself to the system root. This can be very difficult to get rid of. One solution is to reinstall the firmware, but this is easier on some devices (e.g., Nexus or Samsung) than others.