Yes, giving the legs or arms separate animation is what I would do.

Yeah, basically. You're familiar with transparent layers in art software? You want to split it so each movement is on a layer, because it's brain-straining enough to animate a single movement, no one wants to try to do two at the same time in the same image. For a simple example, it's common to have a face with no eyes as one layer, then on top of that a layer of just eyes can be animated to blink or make expressions. Mouth movement for lip synch is handled the same way. You can have as many such layers as you want. A typical 2D avatar for a 2D mmo incorporates hair, weapon, and multiple pieces of clothing all as separate layers, which may have their own animation such as a cloak flapping in the breeze. A run cycle might be slightly more complicated if you want the torso to move up and down or angle forward or backwards, but it can be done. As long as you draw all the pieces you can use a program to display them in whatever combinations you want. If the total number of combinations is small you can merge the layers ahead of time into a standard sprite sheet, but if it is larger you treat each animated part as its own sprite.

A png functions as a single transparent layer but the format does not support multiple layers. To work with multiple layers together you pretty much have to use photoshop format or gimp format, painter might have a similar thing but I'm not familiar with it. Or if you are working in vector I think illustrator's groups can function as layers. The problem is that none of those programs are really aimed at creating animation. Gimp has an animation preview feature but it treats each layer as a frame and doesn't support transparency very well so you have to merge and flatten things to preview them. There are a few 2D programs specifically aimed at creating animation be I'm not personally familiar with them and could not tell you whether they make any use of layers. What's your software of choice?