Coding distortion is a critical factor in video coding algorithms such as rate distortion optimization, rate control and optimal quantization. Accurate distortion estimation without complex pre-coding has always been highly desired. Traditional distortion estimation methods depend roughly on two assumptions-accurate modeling of the DCT coefficients and fine quantization. Unfortunately, these two assumptions may not be satisfied in most video coding situations. This paper proposes two new methods to estimate video coding distortion dropping the above assumptions. The first one is based on function fitting, modeling coding distortion as a function of the ratio of quantization step to the standard deviation of the residual image. The second one is machine learning based, where an ensemble learning model is employed and the feature vector is composed of the distortion of referenced frames, the variance of the residual image and the quantization step. The HEVC reference encoder HM with the hierarchical coding structure is employed for accuracy evaluation. The experimental results show the accuracy of the proposed methods is much higher than that of traditional ones.