I understand that a factory reset is not enough in most cases.
A factory reset is usually enough if performed through Settings, which removes Factory Reset Protection from the device (a reset from Recovery does not do this). This will also unlink Android Device Manager and remove most other tracking tools.
If you are concerned about apps that may have been integrated into the system image, then yes you should flash a custom recovery and then a ROM (selecting the wipe option). Unless there is a malicious bootloader installed (unlikely) then this will more than suffice. You might also want do delete anything from /sdcard
and format any external SD cards just to ensure that no malicious files are left there that you might accidentally use.