With some caveats, you could pull this off declaratively by using a flow (visual workflow) to delete the record.
The flow would create a record in a custom object and would pass the ID of the record being deleted (along w/ any other fields, if needed). The outbound message would be triggered off the custom object via a workflow rule, and an auto-launched flow on the custom object would delete the 'parent' record.
Some things to consider:
You should remove delete permissions from users, as else users could delete from list views, even if you removed the delete button from the page layout.
Alternatively, you may be able to embed the flow in a visualforce page and override the delete button to point to the flow - not sure if that would work though, have not tried it.
I think it would be best if the user-initiated flow checks a custom field on the record to be deleted, as this will respect FLS / CRED / Sharing. Then an auto-launched flow (which runs in system mode) can handle the creation of the custom object record and the deletion of the 'parent' record. So users would not need any CRED on the custom object record.
All in all, it might be easier to pull in a developer to code it up - but this should work.