We present an exact dynamical QCD simulation algorithm for the $O(a)$-improved Wilson fermion with odd number of flavors. Our algorithm is an extension of the non-Hermitian polynomials HMC algorithm proposed by Takaishi and de Forcrand previously. In our algorithm, the systematic errors caused by the polynomial approximation of the inverse of Dirac operator is removed by a noisy-Metropolis test. For one flavor quark it is achieved by taking the square root of the correction matrix explicitly. We test our algorithm for the case of $N_f=1+1$ on a moderately large lattice size ($16^3times48$). The $N_f=2+1$ case is also investigated.