Here is a proof (that positive recurrence suffices). Let be the time of the first transition from i to j, so that . Note that if , and . By Markov property we have, for all , , where the last equality results from the previous remark. Thus,
For to decrease exponentially, it would be sufficient if the last probability is greater than a positive constant, for a positive proportion of indices (we can't expect the probability to be positive for all ).
After a short thought, it appears that the conditional distribution of given is a Markov chain with similar transitions as the initial ones, expect that the transition from i to j is removed and the other transitions starting from i are normalized accordingly. Note that this doesn't work if (i,j) is the only possible transition starting from i, i.e. if ; this special case could be dealt with by modifying the Markov chain at the very beginning so as to "erase the (useless) state i" (it's a bit messy to explain, I hope you get the picture, anyway it's not the crucial part).
So let us consider this new Markov chain (without the transition (i,j)). If the state space was finite, of course it still is finite (same state space), so that the Markov chain still is positive recurrent. In the general case, the Markov chain (restricted to the still accessible states) still is positive recurrent as well, I guess, but I can't think of an argument so I let you figure that out if you want. Therefore, if denotes the period of the new Markov chain (whose law is denoted by ), then for some invariant probability measure , with because i is accessible from the initial state (and where ). So we have a constant and such that, for all , .
This gives the conclusion: we have for all , and for indices that are multiple of ( , and large enough). Hence a geometric(=exponential) rate of decrease (here we use ). If this is not obvious to you, try to prove it.
This should answer your questions; you may ask for additional explanations if you need.