When it comes to guest users, I don’t feel comfortable supporting this on this many websites.
But in case you ask, it could be that for logged-in users, there could be a selector for files already in the media directory. Then if people have the capability for upload_files they can upload first and then select it from that file selector. Somewhat like the classic editor maybe :)
Is that something that would be good enough for you?