This is how I usually start a walk cycle:
Just move around the main mass and figure out the amount of time and space you want to take up.
This would be after removing his limbs, so go ahead and draw them in when designing what he'll look like.
Don't worry about it being perfect, just move stuff around and make something happen.
Then go for the feet.
You can start out by making them all look the same:
The eye is drawn towards objects of focus like hands and feet.
The end of a limb is more important than the limb itself (but of course still important).
The bend of the limb can be determined directly from the placement of the foot.
No need to worry about drawing that now.
Focus on contact.
The feet will generally have more motion and action than the body in this sort of cycle.
This will affect your time and space.
Don't be afraid of this.
Just add new frames where you need more time and move around the body if its position doesn't make sense relative to the feet.
Also I threw these on a new layer just to make things a little more flexible.
Once you get the general idea of your motion we can add more passes to it:
Add the limbs.
Change the form of the feet to better match the action of each frame.
Add follow through elements such as the tail.
Tweak the timing.
More passes could be done to clean up, introduce asymmetrical timing, add the flaming eye fx, etc.
The tail I've done isn't as polished as I'd like but serves as a guide if I were to finish it.
Get used to working in passes.
Every step is a tool to the next.
