Optimizing single-row DELETEs from a table with many FOREIGN KEY references
the situation would greatly improve if I added supporting indexes for all the FK (currently, only 20 of the 60 tables have it)


You should always index fields used as keys, foreign or otherwise. 
This gives the database far more options when analysing how to execute the query and adding them may actually increase the overall performance of your application. 


  many of these FK are for columns like "modified by", so all the indexes would have no other purpose 


As with [pretty much] everything on Planet Database, it's a compromise.
Here, you're balancing data integrity - knowing with certainty who changed something - against speed - not having those extra indexes that slow down inserts. 
Does it really matter if you don't know (with certainty) the user that changed these records?  If not, you're OK as you are.  If it does matter - and in lots of cases, it really, really does - then you're stuck with having the overhead of the indexes. 


  Before running the DELETE, I already make sure that all the referencing records have been deleted ... 


With the FK's in place, you would not be able to delete them anyway, so the values of this activity is dubious. 

The question really should be, why is the delete taking an hour?
If you're only deleting one record out of a million row table and there are no rows in the tables with FK's back to this table, then what's taking the time?  It should be practically instantaneous. 

Slow queries, even deletes, are often caused by missing indexes - are you performing the delete based on the record's Primary Key field?  Or some other combination of [not-indexed] fields?