Can't you use json operators [1] for this?
-- Permanently delete message sent by jon
DELETE from deleted_record where table_name = 'messages' and data->>'sender' = 'jon';
-- Permanently delete message sent by jon
DELETE from deleted_record where table_name = 'messages' and data->>'sender' = 'jon';
It also requires you to scan the entire table and decode JSON for every row you've ever deleted, which may become prohibitively expensive for large databases.
To give an example for your 1st point: If you have the schema users->messages->message_attachments and message_attachments does not store the user_id, you'll have trouble finding all attachments from a specific user.