Thought of random animations a while back as well. Just couldn't be bothered ;P

You specify a percentage of randomness at an animation joint and when the animation is executed the animation at that joint is randomized in any world space direction. e.g. if you melee somebody his elbow will always be in a different place. (If that's what random animation permutations are).