The emission of unburnt exhaust methane from the natural gas-based combustion engines is an important source of greenhouse gas to control. Rutile IrO2 has shown great potential as a methane oxidation catalyst, but further developments for practical use have been slow as the kinetic mechanism and design principles under exhaust conditions are poorly understood. Here, we demonstrate the experiment-validated first-principles-based microkinetic model (MKM) for IrO2 to elucidate the mechanistic insights, and develop the descriptor-based MKM screening pipeline to discover feasible catalysts for methane complete oxidation. The framework uses a minimal number of ab initio descriptors suggested by sensitivity analysis and scaling relations, equipped further with a machine learning model to extend the search space to a larger scale. We search through hundreds of doped rutile oxides by constructing the MKM-based activity map, and suggest promising Pareto-optimum candidates. The proposed workflow can be extended to explore other industrial catalysts under experimental conditions.