It seems that from Android API 23 you must explicitly request a permission for drawing over other apps.
As of API level 23, an app cannot draw on top of other apps unless it declares the SYSTEM_ALERT_WINDOW permission in its manifest, and the user specifically grants the app this capability.
The second requirement (you must send an intent) is very badly implemented as it doesn't popup the new permissions window with Allow/Disallow buttons, but instead sends the user to a completely new settings page where the user must switch a toggle button and then navigate back to get back to the app.
If the second step is not met, the app will throw Unable to add window permission denied for this window type
error.
However - such apps as Twilight or Facebook Messenger do not require user to switch that permission (I was not navigated to that settings screen) and yet they are able to draw over all apps.
How do Facebook, Twilight and similar apps get around this new requirement?