Hi Alex,
The second idea should already be the way it works, if a module or page is marked with edit permissions for Admins only then no-one else should be able to delete it. If it isn't working that way now then I would consider it a bug and fix it so let me know if that is the case and I'll look into it.
I'm also open to the first idea of adding a special permission, if you feel you really need it, it would be easy enough to implement.
Note that when we talk of deleting a module I'm thinking in terms of really deleting it as opposed to just remoiving it from a page which does not really delete it. I think anyone with edit permission on a page should be able to remove a content instance from the page, but again if admin is the only role that can edit then no-one else should be able to edit the page therefore no-one else should be able to remove it from the page.
Best,
Joe