Is there any tool that allows you to mass-delete custom object records using only the External Id on that object record rather than the Salesforce record Id?
I don't think this is possible without a level of complication, no.
Depending on where your list of external ids exist, you could do this using the developer console, and Execute Anonymous Apex.. Load a list of the records you want based on the external id criteria(/data) and then delete said list.
Alternatively, a method we have used before with the Salesforce Dataloader, is to create a new checkbox field on the custom object (defaulted to false). Then, take the CSV of External IDs and use it to perform an update on the records, setting this flag to "true" (so only the listed external IDs are affected). You can then use this flag to determine which records to delete from Salesforce either via the interface, developer console, or using the dataloader again (which is more complicated) to pull out the SF IDs of the "infected" records and then push them back up to a delete command!
Data management is not part of my day to day job, so solutions like the above seem more like the norm to me.