Since the average of the four numbers $4, a, b, 22$ is 13, then $\frac{4+a+b+22}{4}=13$ and so $4+a+b+22=52$ or $a+b=26$. Since $a>4$ and $a$ is an integer, then $a \geq 5$. Since $a+b=26$ and $a<b$, then $a$ is less than half of 26, or $a<13$. Since $a$ is an integer, then $a \leq 12$. Therefore, we have $5 \leq a \leq 12$. There are 8 choices for $a$ in this range: $5,6,7,8,9,10,11,12$. These give the pairs $(a, b)=(5,21),(6,20),(7,19),(8,18),(9,17),(10,16),(11,15),(12,14)$. Thus, there are 8 possible pairs.