Before I found this exploit, I leveled my charm on quests that required the use of dialogue options, like the Kidnapped Daughter and Family Feud. Also, there are chances for charm increase when dealing with enemy lords that are defeated in battle. Sure, you pass up on some money for selling them to the slavers, but you get increased charm and approval from their faction, which can be useful if you intend to start your own kingdom.
I would suggest joining an army as a mercenary earlier on and getting into battles. This should serve 3 purposes. Getting needed experience for your troops, offering your money and influence, and the chance to capture lords, which I found gave me several levels of charm early on by letting them go.
I won't disagree that there ought to be slightly higher gains in charm leveling, but I'd hate to see an exploit be used for that purpose. Anything resolving an issue with conversation instead of getting into combat boosts charm. Hope that helps some.