I have found that the best way to get your agents stronger is to use all of them as much as you can. I usually alt click on the agent tab every turn and cycle through all my agents each turn and find something for each of them to do. I like to train my assasins on rebel captans. I just keep hitting the stack turn after turn. I helps if you do this on forigen soil so the devastation doesn't build up on your own land.
I also keep my diplomats talking to everyone that they meet. Even a failed bribe attempt gives them experience. I keep one or two diplomats wandering about just selling my map. by the time you get back around to a country, you have an updated map that is worth more than it was last time, and you are building uber-diplos at the same time. I then put the ubers on the front lines to extract tribute form my enemies. Sometimes a whole turn will be composed of just dealing with my agents.