From a quick look there is a dedicated delete_attachment action in wp_delete_attachment() function, it gets passed an ID of attachment being deleted.
However I am not completely confident that this covers all cases. There is a fair amount of duplication in WP’s post–related APIs and similar tasks might be performed by different functions in different places.
I would start with this hook and experimentally check if it’s sufficient for desired scenarios.