Reproductions steps:
1) Create a new project or open any existing one
2) Click on "Build and run" button and run the app on Android device with 4.1 OS version
-- Notice that Editor succeeds and doesn't show any error messages
-- Notice that Application was not even installed on a device

Note: as this issue was discovered and tested together with issue 1086401 I couldn't test this case for regression on versions which did not reproduce mentioned bug

Reproduced on: Unity 2019.1.0a2, 2018.3.0b4, 2018.3.0b1, 2018.3.0a4
Unable to reproduce on: Unity 2018.2.10f1, 2018.3.0a1, 2018.3.0a3 - builds and runs succesfully on a device

Devices under test:
Reproduced with:
VLNQA00055, Samsung Galaxy S3 (SC-06D), Android 4.1.2, CPU: Snapdragon S4 Plus MSM8960, GPU: Adreno (TM) 225
VLNQA00040, Htc ONE S (HTC One S), Android 4.1.1, CPU: Snapdragon S4 MSM8290, GPU: Adreno (TM) 225

Unable to reproduce with:
VLNQA00134, Samsung Galaxy S8 (SM-G950F), Android 8.0.0, CPU: Exynos 9 Octa 8895, GPU: Mali-G71
VLNQA00016, Samsung Galaxy S4 Mini (GT-I9195), Android 4.4.2, CPU: Snapdragon S4 Plus MSM8960, GPU: Adreno (TM) 305
VLNQA00106, Samsung Galaxy S2 Plus (GT-I9105P), Android 4.2.2, CPU: Broadcom BCM28155, GPU: VideoCore IV HW
VLNQA00048, Samsung Galaxy S3 (GT-I9300), Android 4.3, CPU: Exynos 4 Quad 4412, GPU: Mali-400 MP