I'm thinking of a way to redirect from deleted pages to an existing page using 301 permanent redirect.
It is ok if deleted pages are in the bin.
Can you give me some general ideas how to override existing handlers or what else I can do?
Here's a reponse to that question that was posted a few years back -- I hope it helps: https://world.episerver.com/forum/developer-forum/Developer-to-developer/Thread-Container/2009/10/Reference-to-deleted-pages/
There also exists a tool by Huilaaja that does 301 redirects. See his blog post and/or GitHub page. This might not directly solve your case but might give you pointers. I believe with this tool you could create the desired effect that when page is moved to waste basket you can programmatically create a redirect to something else. But have a look this.
Another tool might be the 404Handler by Geta. Not directly answering what you are looking for but maybe something that you might want to use if you change your "requirement".
We use the Geta tool as Antti mentioned and it works well