Best Approach to all unique groups of users to edit unique groups of entries in 1 channel
If you're not using Craft's user groups for permissions, the solution you suggest is more or less exactly what sprung to my mind. You could create a Category Group called Permissions (just to keep it distinct from Craft's internal user groups), add the initial permission categories that are needed, then create a new field named Permissions that can be added to the User field layout and the field layout for the sections that are being managed.
Each entry can have one or more Permissions categories selected in the Permissions field, and every User can have one or more Permissions categories assigned to them in their profile.
To work out whether the user can edit a particular entry, just check that their permissions match the permissions that are set for that entry. This is probably easiest with IDs:
{% set entryPermissionIds = entry.permissions.ids() %}
{% set userPermissionIds = currentUser.permissions.ids() %}
{% set canEdit = false %}

{# 
    If the result of intersecting the user's permission IDs array with the
    entry's permission IDs array is equal to the length of the entry's 
    permission IDs array, the user has all the correct permissions to edit 
    this entry
#}
{% if userPermissionIds|intersect(entryPermissionIds)|length == entryPermissionIds|length %}
    {% set canEdit = true %}
{% endif %}

{% if canEdit %}
    {# Show edit form #}
{% endif %}

Note: I've not tested this code, but I think the principle is sound!