Marking grub.cfg read only doesn't work - I tried that at first.

I make a backup copy of my grub.cfg before doing kernel updates, run the updates and update-grub as normal, then compare the changes to the backup, and manually re-edit where needed to ensure smooth booting - before I ever boot a new kernel, and so far, I haven't had any problems.

Part of my final solution ("Final Solution") was to create a dedicated boot partition, install grub2 to it, allow it to run update-grub to write the changes, run blkid to get the correct UUIDs, then manually edit grub.cfg to correct the UUIDs referenced incorrectly to the ones they should have been.

Here's my grub.cfg (in part), starting at about line 149, which I modified using the above approach, and which allows me to boot between Ubuntu and Kali, complete with the "safe mode" option for each:

set linux_gfx_mode=keep
export linux_gfx_mode
menuentry 'Ubuntu' --class ubuntu --class gnu-linux --class gnu --class os $menuentry_id_option 'gnulinux-simple-883242e7-e8da-40d2-aab7-40a2f771aa6b' {
    recordfail
    savedefault
    load_video
    gfxmode $linux_gfx_mode
    insmod gzio
    if [ x$grub_platform = xxen ]; then insmod xzio; insmod lzopio; fi
    insmod part_msdos
    insmod ext2
    set root='hd0,msdos4'
    if [ x$feature_platform_search_hint = xy ]; then
      search --no-floppy --fs-uuid --set=root --hint-bios=hd0,msdos4 --hint-efi=hd0,msdos4 --hint-baremetal=ahci0,msdos4  dcd42ae2-281e-4101-9d64-fb0301c6eb37
    else
      search --no-floppy --fs-uuid --set=root dcd42ae2-281e-4101-9d64-fb0301c6eb37
    fi
    linux    /vmlinuz-4.4.1-040401-generic root=UUID=883242e7-e8da-40d2-aab7-40a2f771aa6b ro   crashkernel=384M-:128M
    initrd    /initrd.img-4.4.1-040401-generic
}
submenu 'Advanced options for Ubuntu' $menuentry_id_option 'gnulinux-advanced-883242e7-e8da-40d2-aab7-40a2f771aa6b' {
    menuentry 'Ubuntu, with Linux 4.4.1-040401-generic' --class ubuntu --class gnu-linux --class gnu --class os $menuentry_id_option 'gnulinux-4.4.1-040401-generic-advanced-883242e7-e8da-40d2-aab7-40a2f771aa6b' {
        recordfail
    savedefault
        load_video
        gfxmode $linux_gfx_mode
        insmod gzio
        if [ x$grub_platform = xxen ]; then insmod xzio; insmod lzopio; fi
        insmod part_msdos
        insmod ext2
        set root='hd0,msdos4'
        if [ x$feature_platform_search_hint = xy ]; then
          search --no-floppy --fs-uuid --set=root --hint-bios=hd0,msdos4 --hint-efi=hd0,msdos4 --hint-baremetal=ahci0,msdos4  dcd42ae2-281e-4101-9d64-fb0301c6eb37
        else
          search --no-floppy --fs-uuid --set=root dcd42ae2-281e-4101-9d64-fb0301c6eb37
        fi
        echo    'Loading Linux 4.4.1-040401-generic ...'
        linux    /vmlinuz-4.4.1-040401-generic root=UUID=883242e7-e8da-40d2-aab7-40a2f771aa6b ro   crashkernel=384M-:128M
        echo    'Loading initial ramdisk ...'
        initrd    /initrd.img-4.4.1-040401-generic
    }
    menuentry 'Ubuntu, with Linux 4.4.1-040401-generic (upstart)' --class ubuntu --class gnu-linux --class gnu --class os $menuentry_id_option 'gnulinux-4.4.1-040401-generic-init-upstart-883242e7-e8da-40d2-aab7-40a2f771aa6b' {
        recordfail
    savedefault
        load_video
        gfxmode $linux_gfx_mode
        insmod gzio
        if [ x$grub_platform = xxen ]; then insmod xzio; insmod lzopio; fi
        insmod part_msdos
        insmod ext2
        set root='hd0,msdos4'
        if [ x$feature_platform_search_hint = xy ]; then
          search --no-floppy --fs-uuid --set=root --hint-bios=hd0,msdos4 --hint-efi=hd0,msdos4 --hint-baremetal=ahci0,msdos4  dcd42ae2-281e-4101-9d64-fb0301c6eb37
        else
          search --no-floppy --fs-uuid --set=root dcd42ae2-281e-4101-9d64-fb0301c6eb37
        fi
        echo    'Loading Linux 4.4.1-040401-generic ...'
        linux    /vmlinuz-4.4.1-040401-generic root=UUID=883242e7-e8da-40d2-aab7-40a2f771aa6b ro   crashkernel=384M-:128M init=/sbin/upstart
        echo    'Loading initial ramdisk ...'
        initrd    /initrd.img-4.4.1-040401-generic
    }
}
menuentry 'Kali GNU/Linux Rolling (kali-rolling) (on /dev/sdj2)' --class gnu-linux --class gnu --class os $menuentry_id_option 'osprober-gnulinux-simple-c5f8b7c2-82b6-4c22-a69e-6b4954ee5d5f' {
    savedefault
    insmod part_msdos
    insmod ext2
    set root='hd0,msdos4'
    if [ x$feature_platform_search_hint = xy ]; then
      search --no-floppy --fs-uuid --set=root --hint-bios=hd0,msdos4 --hint-efi=hd0,msdos4 --hint-baremetal=ahci0,msdos4  dcd42ae2-281e-4101-9d64-fb0301c6eb37
    else
      search --no-floppy --fs-uuid --set=root dcd42ae2-281e-4101-9d64-fb0301c6eb37
    fi
    linux /vmlinuz-4.0.0-kali1-amd64 root=UUID=c5f8b7c2-82b6-4c22-a69e-6b4954ee5d5f ro crashkernel=384M-:128M
    initrd /initrd.img-4.0.0-kali1-amd64
}
menuentry 'Kali GNU/Linux Rolling (kali-rolling) (on /dev/sdj2) (recovery mode)' --class ubuntu --class gnu-linux --class gnu --class os $menuentry_id_option 'gnulinux-3.16.7-031607-generic-recovery-c5f8b7c2-82b6-4c22-a69e-6b4954ee5d5f' {
    recordfail
    load_video
    insmod gzio
    if [ x$grub_platform = xxen ]; then insmod xzio; insmod lzopio; fi
    insmod part_msdos
    insmod ext2
    set root='hd0,msdos4'
    if [ x$feature_platform_search_hint = xy ]; then
      search --no-floppy --fs-uuid --set=root --hint-bios=hd0,msdos4 --hint-efi=hd0,msdos4 --hint-baremetal=ahci0,msdos4  dcd42ae2-281e-4101-9d64-fb0301c6eb37
    else
      search --no-floppy --fs-uuid --set=root dcd42ae2-281e-4101-9d64-fb0301c6eb37
    fi
    echo    'Loading Kali Linux 4.0.0-kali1-amd64 ...'
    linux /vmlinuz-4.0.0-kali1-amd64 root=UUID=c5f8b7c2-82b6-4c22-a69e-6b4954ee5d5f ro recovery nomodeset
    echo    'Loading initial ramdisk ...'
    initrd /initrd.img-4.0.0-kali1-amd64
}

Your UUIDs should be different, unless you cloned the partition, then you'll have to change the UUID on one of them, and I would use gparted for that, and yes, I've encountered duplicate UUIDs when working with partitions - it really screws things up. Editing grub.cfg isn't the arduous chore many people think it is. Using a text editor with a search function will do the trick. Just remember that some of those UUIDs need to remain unchanged or you're just doing the same thing update-grub does when it changes them all to be the same.

For using LILO, you'd need to employ a similar approach to the one I've suggested, except that I haven't used LILO since Red Hat 5.1.