The best solution that is good enough for 99% of cases is to save the AABBs at different frame intervals (granted, you need to do software skinning first) store them (e.g. in the mesh file), and then linearly interpolate between those AABBs.
I wouldn't do that, just go for a static AABB as mentioned before.
What you can do is simply rotate your model in bind pose in some loop or so, and find the maximum AABB, this works pretty well.
Storing AABB's and interpolating them is really overkill, and you need to pass it around your blend trees and handle all the blending and logic in there as well then to get the right AABB. It isn't really worth it I think. Then you could also just build the bounds from the transformed obb's at the end. I doubt that is much slower than this with large blend trees involved.