Interval arithmetic offers a powerful tool for structural model updating when uncertain-but-bounded parameters are considered. However, the application of interval model updating for practical engineering structure is hindered due to model complexity and huge computational burden involved in the repeated evaluations of non-probabilistic constraints. In this light, an efficient inner-outer decoupling scheme is proposed for non-probabilistic model updating in this study. The mathematical operation of interval model updating is decomposed into two layers labelled as inner layer with the operation of uncertainty propagation and outer layer with the operation of interval optimization. In the inner uncertainty propagation, the High Dimensional Model Representation (HDMR) is utilized to enable the decomposition of the model outputs in terms of multivariate inputs into the sum of multiple single-variate functions, which is further approximated by Chebyshev polynomials so that the stationary points of each function can be derived. In the outer layer, a fast-running optimization strategy based on the stationary points of Chebyshev polynomial approximation is proposed to accelerate tracking the bounds of model parameters by avoiding time-consuming brute-force interval optimization. As a result, the original non-probabilistic updating process with two interacted layers can be completely decoupled into two independent operations of the inner uncertainty propagation and outer interval optimization so as to enhance the search efficiency and convergence rate significantly. Two numerical case studies illustrate capability of the proposed method in updating the structural parameters intervals efficiently with the model outputs intervals agreeing well with the testing outputs intervals. Two experimental cases of steel plates and the Canton Tower also demonstrate the efficiency and advantages of the method in interval model updating.