There's indeed an example of such a function.
Given a an infinite subset $I\subset\omega$, call indexation of $I$ the unique increasing bijection $\omega\to I$. If $(x_n)$ is its indexation, define $f_I$ the permutation of $I$, mapping $x_1\mapsto x_0$, $x_{2n+1}\mapsto x_{2n-1}$ ($n\ge 1$), $x_{2n}\mapsto x_{2n+1}$ ($n\ge 0$). Hence $f_I^k$ maps $f_{2n+1}\mapsto f_{2n+1-2k}$ for $n\ge k$, maps $f_{2n+1}\mapsto f_{2k-2n-2}$ for $0\le n\le k-1$, and maps $f_{2n}\mapsto f_{2n+2k}$.
Say that a subset $I$ of $\omega$ is "good" if it is infinite, and, $(x_n)$ being its indexation, it satisfies $x_n>2x_{n-1}$ for all $n\ge 1$. If $I$ is good, then $\min_n|x_n-f_I^k(x_n)|=x_{k+1}-x_k$, and $(x_{k+1}-x_k)$ is strictly increasing.
Given a partition $\mathcal{P}$ of $\omega$ into good subsets, let $f$ be the permutation of $\omega$ whose restriction to $I$ is $f_I$ for every $I\in\mathcal{P}$. Then $(\min_n|x_n-f^{k}(x_n)|)_k$ is strictly increasing. The existence of such a partition is obtained by a straightforward induction.
