The following is an attempt at a combinatorial characterization.
Lets call a directed graph $G=(V,E)$ multipartite if its vertex set $V$ can be partitioned into subsets $V_0, \ldots, V_{k-1}$ such that all the edges originating in $V_i$ lead to $V_{i+1 {\rm mod }~k}$. Consider the directed graph $G$ associated with the Markov chain $P$: we put the edge $(i,j)$ in $G$ whenever $p_{ij}>0$.
Claim 1: If $G$ is strongly connected, then $\lim_n P^n$ exists if and only if $G$ is not multipartite.
Proof: In one direction, its quite easy to verify that if $G$ is multipartite, $P^n$ does not have a limit.
Conversely, suppose that $G$ is not multipartite. Since $G$ is strongly connected (i.e., $P$ is irreducible), a result of Frobenius (the "Frobenius form" on page 680 here) implies that $P^m$ is a positive matrix for some power $m$, which, as Geoff Robinson explained, yield the desired conclusion.
Next, what about the more general case when $G$ is not necessarily strongly connected? Consider the graph obtained by collapsing every strongly connected component of $G$ into a vertex. Some of these "super-vertices" must have no incoming edges; let $g_1, g_2, \ldots, g_k$ be an enumeration of them. Then the graphs which collapsed to them - $G_1, \ldots, G_k$ - must be strongly connected subgraphs of $G$.
Claim 2: $\lim_n P^n$ does not exist if and only if at least one of $G_1, \ldots, G_k$ is multi-partite.
Proof: Again, if some $G_i$ is multipartite, its easy to see $P^n$ has no limit.
Conversely, suppose no $G_i$ is multipartite. We will next argue that $P^n$ has a limit.
Let $S$ be the set of vertices belonging to some $G_i$, and $S^c$ be the other vertices.
Let $x$ be a nonnegative vector that sums to $1$. We have that if $i \in S^c$, then $\lim_n (x P^n)_i = 0.$ This follows by a probabilistic argument - every certain number of steps there is a positive probability of escaping to $S$ and staying there forever so the probability of staying in $S^c$ must approach zero.
Now suppose $i \in S$; actually, for concreteness, lets suppose $i \in G_1$. Let $A_{n/2}$ be the event that starting from initial distribution $x$, the Markov chain reaches $G_1$ (and consequently stays there forever) by time $n/2$. Then $\lim_n (x P^n)_i = P(A_{n/2}) P( \mbox{being at } i \mbox{ at time } n | A_{n/2}) + P_3(n) $ where $P_3(n)$ is something that goes to zero as $n \rightarrow \infty$ by the previous paragraph. Its not hard to see that each of the first two terms in the previous equation approaches a limit as $n \rightarrow \infty$ - the first approaches the probability of eventual absorption into $G_1$; and the second approaches a limit because $P$ restricted to $G_1$ is strongly connected, and this is where we use Claim 1.
Finally, if $x P^n $ has a limit for every $x$ which is nonnegative and has components which sum to $1$, then by taking $x=e_j$ for every $j$ we see that $P^n$ has a limit. That concludes the proof.
Things are a bit simpler in the case when $G$ is an undirected graph (i.e., if $p_{ij}>0$ implies p_{ji}>0) since an undirected graph splits up into connected components and is multipartite if and only if it is bipartite. Thus:
Claim 3: If $G$ is undirected, $\lim_n P^n$ does not exist if and only if one of the connected components of $G$ is bipartite.