What I am trying to figure out is if there is a way to allow the player to open up the menu to choose a new perk without having to level. Before anyone says that you could probably use the console to open the menu here's the catch, I want to tie in the acquisition of the new perk to one of three things: completing a repeatable quest (similar to the go kill X or do Y for reward quests), paying a very large amount of caps for an item that would open the menu and allow the selection of one perk per item purchased (one use item), or through a dialog option with an NPC 'trainer' that would take a similarly large amount of caps from you and let you choose a perk to get trained in.
This way level capped characters, or even non level capped characters that are able to get the required caps or complete the quest, would be able to obtain more perks rather than just at level or through cheating.
I believe that by having it open up the perk menu it would still impose all level, S.P.E.C.I.A.L., and skill requirements of each perk. You'd still have to meet the requirements, but wouldn't have to wait to level up.