We propose a two-stage gait pattern generation scheme for the full-scale humanoid robots, that considers the dynamics of the system throughout the process. The fist stage is responsible for generating semi-dynamically consistent step position and step time information, while the second stage incorporated with multi-body dynamics system is responsible for generation of gait pattern that is feasible and stable on the full-scale multi-degree-of-freedom humanoid robot. The approach allows for very rapid gait pattern regeneration during the swing phase of motion and includes information about present dynamic state when regenerating the new pattern. The paper contains description of a developed method, as well as experimental results proving its effectiveness.