Now that all pieces are in place we can go and improve stuff. It seems that the most stable way of walking the way cats do is to have long strides (another parameter to be passed in walking gait). Long strides make good 'triangles': when the front leg is moving near the last position while back lag is travelling through the air to almost meed front leg all one one side. That way the front leg one that side plus two legs on the other side form perfect triangle which contains centre of the body.
When the front and back leg meet, the front leg can then move forward while the back leg creates a very similar triangle which will still hold the centre of the body while the body travels forward. Only near the end of the front leg's travel through the air - towards the front most position, the centre of gravity would fall out of the 'back' triangle and the whole robot would tip forward. Fortunately, that happens just as the front leg was going down towards its front most position. When that happens, the whole process repeats with opposite side back leg that reaches last position and is ready to travel forward to meet its front leg.
Next is going to be adding gamepad and allow remote control!