Hey,
One tip I can offer when approaching this problem is to make sure to break the code down to the absolute smallest reproduction of the problem. It really helps to only have to think about a small amount of logic as opposed to superflous code. Your example, for instance, had extra logic that is not related to the problem and just means more code has to be looked at to hunt down the cause.
I reduced your code to the minimum and then focused on the QCustomMenu.contextMenuEvent implementation. Printing out the value of the captured action, parent, self, etc, I was able to see that the problem is that your rename callback is operating on the menu itself, as opposed to the action. What you probably wanted to do is to rename the action text if the right click was on an action item, or to rename a menu if the action is actually a menu (menus are wrapped in an action).
We first look up the action at the event position. If there is no action it means we right clicked the actual menu area, so we extract the action from that. Either way, we pass that on to be renamed as an action.
Some other tips about your original code. Be a bit careful with assigning parents to menus if they are temporary model menus that you exec_() and throw away. The parent relationship can make them stay alive and leak. So you can still parent the menu to get the right relative position, but you should deleteLater() to clean them up. And the use of the custom QAction subclasses just to be able to compare them, even though they have no custom behaviour, could probably be replaced by just creating a set of constants; AddType=1, RemoveType=2, ..., and then using action.setData() and action.data().toInt() in order to check the type. Its up to you really. Its easier than having a bunch of subclasses that don't do anything.
Justin