Best way to handle "climbing" an animated skinned mesh?

I'd like to accomplish something like Shadow of the Colossus style climbing an animated giant.

Due to the size of the creatures, simply parenting primitives to the creature's bones will not suffice. The climbable surface needs to be nearly 1:1 with the skin.

Its pretty easy to forcibly recalculate the collision mesh to match the animated SMR (as seen here), and given that there will never be more than one creature on screen, it doesn't perform too terribly, but I'm open to suggestions.

But as for the actual climbing, the character will need to not just get the point on the animated mesh, but also move with the animation, while climbing. I'm pretty stumped on how to figure that one out.

I thought about maybe just figuring out the initial "climb" raycast hit position relative to the position of the nearest bone of the animated mesh, and keeping the character positioned with that, but it would get slippery in-between bones I think.

I also thought about figuring out the triangle from the hit triangle index, then calculating the position within the triangle, and keeping the character in-line with that, but I'm not sure how to go about it and I think it might be terribly CPU intensive.

Any thoughts?