Решение оказалось тривиально:
File/Settings > Build,Execution,Deployment/Instant Run - Снять флаг "Instant run...".
Instant run ускоряет работу с новыми устройствами, на которых API выше 20, для более старых он всё-равно почти бесполезен.
После этого нужно создать конфигурацию (можно скопировать имеющуюся) и, переключаясь на разные конфигурации, можно независимо запускать выполнение/отладку на различных устройствах одновременно.