Some things to think about.
You may not need special permissions for each user/group for the media library if they don't have Editor status (can't access the Kentico CMS admin area), even a unique media library for each user.
If they don't have Kentico admin accesses, one simple solution would be to have a single Media Library ("User Uploaded Content"), with either of these structures:
-UserUploadedContent
-Images
-Bob
-Videos
-Bob
-Audio
-Bob
OR
-UserUploadedContent
-Bob
-Images
-Videos
-Audio
Then all you need to do is create a page where they can upload a file, and you programatically (using the API) place the file in the proper folder using their username. They can't Edit / Delete, right? so this makes it easy.
If they do need Delete capabilities, again you could just do this with a custom screen, Repeat all files found in the path matching their username, and provide a Delete button control that will delete that file (again using the API).
Does this solve it, or do they have Admin access?