create 2 groups of characters. update one set of skins one frame, the rest on the next frame. The update frequency of each model will remain exactly the same, however your frame rate will have doubled. Generally it's still a good idea to update the animation hierarchy each frame though.

How does this keep the update rate the same? Or do you mean double buffering?
It means you are updating every second frame instead of every frame. In that case it is also not that useful to update the animation hierarchy, as you can just use a bigger delta time, and the bone transforms aren't needed every frame for skinning then anyway. Unless you do visibility checks based on the bounds calculated by the hierarchy or so, but for that you wouldn't need the entire hierarchy to be updated in most cases. Unless you don't have skinned objects, but then there is no real performance cost anyway for updating every frame.