What is the difference between a non-stationary policy and a state that stores time?
So, here's is the question: Is it true that a non-stationary policy must satisfy this condition?
  
  $$ \forall i, j \in \mathbb{N}, s \in S, \pi (i, s) = \pi(j, s) $$


With your custom notation (which certainly isn't common, but seems reasonable)... I assume you meant to say that a stationary policy must satisfy that condition, rather than that a non-stationary policy must satisfy that condition. In that case, yeah, that seems correct to me. A stationary policy would satisfy that condition, and a non-stationary one wouldn't.



Wrapping back to the more usual notation, where $\pi(S, A)$ denotes a probability of selecting $A$ in $S$ (which also still covers the case of a deterministic policy, which would simply assign a probability of $1$ to a single action, and $0$ to all others)... I think it's still interesting to consider the case where we decide to "bake" a time-step counter into the state representation.

With this notation, for two different time steps $t$ and $t'$, such that $t \neq t'$, I'd say that a policy $\pi$ is stationary if and only if:

$$\pi(S_t, A_t) = \pi(S_{t'}, A_{t'}) \text{ if } S_t = S_{t'} \wedge A_t = A_{t'}.$$

Note that if we decide to include $t$ in the state-representation, the case that $S_t = S_{t'}$ with $t \neq t'$ will actually never hold within the same episode, states at different time steps will always automatically be different from each other if the time step is one of the "features" encoded in the state. So, within a single episode a policy with a "time-aware" state representation will always automatically be stationary because there cannot be any repeating states. Of course, if you start looking across multiple different episodes, this can change; this is what you're doing when you write:


  Once we reset the environment to evaluate the policy again, the turn, which we store in the state, will go back to 0, but the background number of evaluations won't reset and it will be 3.


If you chose to also embed that "episode counter" into the state representation, you would also no longer have any state repetitions at all anymore across different episodes (I don't think doing this would ever be a good idea though).