Register for NSManagedObjectContextObjectsDidChangeNotification:
[[NSNotificationCenter defaultCenter] addObserver: self
                                         selector: @selector(mocDidChangeNotification:)
                              name:NSManagedObjectContextObjectsDidChangeNotification
                                           object: nil];
And parse the userInfo dictionary in the corresponding method:
- (void)mocDidChangeNotification:(NSNotification *)notification
{
    NSManagedObjectContext* savedContext = [notification object];
    // Ignore change notifications for anything but the mainQueue MOC
    if (savedContext != self.managedObjectContext) {
        return;
    }
    // Ignore updates -- lots of noise from maintaining user-irrelevant data
    // Set actionName for insertion
    for (NSManagedObject* insertedObject in 
           [notification.userInfo valueForKeyPath:NSInsertedObjectsKey])
    {
        NSString* objectClass = NSStringFromClass([insertedObject class]);
        savedContext.undoManager.actionName = savedContext.undoManager.isUndoing ? 
            [NSString stringWithFormat:@"Delete %@", objectClass] : 
            [NSString stringWithFormat:@"Insert %@", objectClass];
    }   
    // Set actionName for deletion
    for (NSManagedObject* deletedObject in 
           [notification.userInfo valueForKeyPath:NSDeletedObjectsKey])
    {
        NSString* objectClass = NSStringFromClass([deletedObject class]);
        savedContext.undoManager.actionName = savedContext.undoManager.isUndoing ? 
            [NSString stringWithFormat:@"Insert %@", objectClass] : 
            [NSString stringWithFormat:@"Delete %@", objectClass];
    }
}
I've tested this in my own code-- it's rough.  Can spend a lot more time making the actionName nicer.  I deleted parsing of updates because: 1) insertions and deletions of objects in to-many relationships generate updates of other objects 2) I don't care to figure out how to discover what properties changed at this time
I also have class names that aren't user-friendly, so this is a great time to implement the description function for all entities, and use that rather than the class name.
But this at least works for all object controllers in a project, and easily enough for insert and delete.
[edit] Updated with mikeD's suggestion to cover redo having an inverse name.  Thanks!