Age of information (AoI) is a powerful metric to evaluate the freshness of information, where minimization of average statistics, such as the average AoI and average peak AoI, currently prevails in guiding freshness optimization for related applications. Although minimizing the statistics does improve the received information's freshness for status update systems in the sense of average, the time-varying fading characteristics of wireless channels often cause uncertain yet frequent age violations. The recently-proposed statistical AoI metric can better characterize more features of AoI dynamics, which evaluates the achievable minimum peak AoI under the certain constraint on age violation probability. In this paper, we study the statistical AoI minimization problem for status update systems over multi-state fading channels, which can effectively upper-bound the AoI violation probability but introduce the prohibitively-high computing complexity. To resolve this issue, we tackle the problem with a two-fold approach. For a small AoI exponent, the problem is approximated via a fractional programming problem. For a large AoI exponent, the problem is converted to a convex problem. Solving the two problems respectively, we derive the near-optimal sampling interval for diverse status update systems. Insightful observations are obtained on how sampling interval shall be tuned as a decreasing function of channel state information (CSI). Surprisingly, for the extremely stringent AoI requirement, the sampling interval converges to a constant regardless of CSI's variation. Numerical results verify effectiveness as well as superiority of our proposed scheme.