What are the requirements of newly added
Like, is adding it to manifest enough (like with internet-permission), or do I need to show dialog for said permission, like we do for storage-permission (in newer Android-versions)?
QUERY_ALL_PACKAGES has a protection level of
normal, so all that you need in the app itself is the manifest entry.
Note that your desired app distribution channel may require you to complete a form documenting why you feel that your app needs this permission, and they may elect to not distribute your app.