Primarily for older phones

I only encountered the App not installed error when trying to install an apk on my phone which runs on 4.4.2 aka KitKat, but my friend did not encounter this error on his phone which runs on 6+. I tried the other solutions such as removing the old/debug version of the app because the apk was a release version, clearing the debug app's data, and even clearing all of my cached data. Then, finally I realized all I had to do was select both signature versions when building my signed apk.

Before I only had V2 (Full APK Signature) selected, but after selecting V1 Jar Signature as well, I was able to successfully install my signed APK on my 4.4.2 device. Hope this helps others!

For me, On Android 9 (API 28), disabling Google Play Protect from play store app worked the trick, and i was able to get rid of the App not Installed error.

To disable Google Play Protect. Open "Play Store" application => tap on Menu button => select "Play Protect" option => Disable the options "Scan device for security threats".

I had a similar issue and it was because I was trying to install an apk on a phone with a previous version of the same apk, and both apks hadn't been signed with the same certificate. I mean when I used the same certificate I was able to overwrite the previous installation, but when I changed the certificate between versions, the installation was not possible. Are you using the same certificate?