The permeability of coal is a critical parameter in estimating the performance of coal reservoirs. Darcy’s law describes the flow pattern that the permeability has a linear relationship with the flow velocity. However, the stress induced deformation and damage can significantly influence the gas flow pattern and permeability of coal. Coals from Songzao coalfield in Chongqing, southwest China were collected for the study. The gas flow velocities under different injection gas pressures and effective stresses in the intact coal and damaged coal were tested using helium, incorporating the role of gas flow pattern on the permeability of coal. The relationships between the flow velocity and square of gas pressure gradient were discussed, which can help us to investigate the transformation conditions of gas linear flow and gas nonlinear flow in the coal. The results showed that the gas flow in the intact coal existed pseudo-initial flow rate under low effective stress. The low-velocity non-Darcy gas flow gradually occurred and the start-up pressure gradient increased in the coal as the effective stress increased. The gas flow rate in the damaged coal increased nonlinearly as the square of pressure gradient increased under low effective stress. The instability of gas flow caused by high ratio of injection gas pressure over effective stress in the damaged coal contributed to the increase of the gas flow rate. As the effective stress increased, the increase of gas flow rate in coal turned to be linear. The mechanisms of the phenomena were explored according to the experimental results. The permeability of coal was corrected based on the relationships between the flow velocity and square of gas pressure gradient, which showed advantages in accurately estimating the performance of coal reservoirs.