Det är väl bara att köpa en telefon som är relativt enkel att låsa upp bootloadern på, sedan installera valfri custom-rom? Detta har ju varit möjligt sedan i alla fall Android 4. Höll själv på väldigt mycket med det runt S2-S6-eran av telefoner; CyanogenOS och ViperOS var rätt trevliga saker, särskilt ihop med ClockworkMods och TitaniumBackups.
Som du säger kring Samsung och Knox kan det vara lite (väldigt) problematiskt nu för tiden, men finns tillverkare som gör det enklare än andra, exempelvis Motorola med Razr-telefonerna. Även OnePlus-mobilerna har jag hört ska vara relativt enkla att roota. Länge sedan jag höll på, men är rätt säker på att XDA-forumet (eller SweClockers egna forum) kan hjälpa dig framåt