EDIT: I have found out how to solve the 'administer users permission needed' problem so I don't really need to know the answer for this. I will not delete the question however, since I would like to know the answer out of curiosity anyway.
Because of this I need to give the permission 'administer users' to everyone while still being able to manage access to individual users (to their view and edit pages as well as to their cancellation).
Therefore I need to restrict users with 'administer users' permission to be able to edit just certain users (based on their id and the id of the user that is to be viewed or edited). (the access function itself is not the problem I already have that one)
I thought about doing something like 'Administer Users by Role' plugin but as it seems there are just too many potential security issues there (the 'administer users permission' is not used only in access to user edit/view but e.g in access to user fields settings page as well.