Can not install my own generated apk

For me, selecting Signature Version v1 and v2 both solved the problem

I found a solution but I still have no idea what caused the problem.

somewhere on my device my app was still installed even though it didnt show up in the app drawer and the play store told me the same. In the settings/apps menu my app was still present (as i mentioned in the edit of my original post) so i clicked on it. If you click on the menu button you can chose unisntall for all users which did the trick. now I can install my apk again.

I have no idea how this happened but there you go, i hope this helps.

EDIT:

I had the same problem as this guy had. the accepted answer over there is much nicer than my poorly foramtted text ;)

"You cannot install this app because another user has already installed an incompatible version on this device"

Your signature changed, so as you mentioned you must uninstall the previous version. You tried to uninstall from the device UI and that fails - so try it from the command-line:

adb uninstall your_package_name

Seen on Nexus devices, occasionally only command-line uninstalls work.

I was facing same problem And I solved it this way, For Current Updated Android Studio 2.3

1. Build > Generate Signed apk.
2. Create Keystore path.
3. Put Password, alias, key password.
4. Build type select accordingly(eg to release in playstore use release).
5. Signature Version select both V1 and V2 checkboxes.
6. Finsih.
7. Go to the apk from explorer and use it for your playstore or in devices as Signed and Certified apk file.