Assasins are great if you use them right. To be effective, they need at least 8 stars. Build up their skill by taking out any enemy diplomats that wonder onto your land. Killing rebel captains is also useful.
Eventually you'll get some retinues. Pet Monkey and Catamite give you +1 skill, and Dancer gives +2. You can get +5 in learned skill traits, plus up to a +3 skill birth trait. This comes out to 11 skill points. (10 might be the max, im not sure)
Once your assasin is skilled, group him with a spy and move them to your enemy's city. Send in the spy first, so you can see all the city's generals and buildings. If you don't send in a spy, some of the generals/buildings will show as question marks, and you won't know what you're attacking or the % success rate. (though with 10 stars you usualy don't need to worry)
Try assasinating all of a faction's family members. It's hard to do, but if you succeed all their lands and armies will turn into rebels.
You'll probably notice that once you get a faction down to 1 or 2 members, new AI generals will seem to pop up out of nowhere. This is because when the AI gets low on generals it marrys off all it's unwed women. It's not the AI cheating as your faction does the same thing. All new generals pop up in the enemy's capital so just send your assasin there and finish the job.