Stop the presses! I've figured it out. It came to me in a dream. It's a great solution, or, if not a solution, then a really good start.
Currently, lieutenants & overlords drop special enchant containers. Did you know that they stay there forever, for all players to pick up? So... why not just say that after the overlord boss room gets loaded into memory, the enchant containers warp to the settlement, for easy access to any new character. BOOM.
All new characters get 1 new enchant for each lieutenant killed, and 3 for each overlord. You are adding absolutely nothing to the game at all that the players couldn't already get if they realized that going to the defeated overlord room would net them 3 free (good) enchants, you're just making it more accessible.
I AM BRILLIANT