Thanks everyone for your replies! As Darij suggested in his answer, it appears the clever trick used in [Gert Almkist's generalisation of a mistake of Bourbaki][1] can be generalised to tackle the problem. Thanks Darij for the suggestion and for the reference.

If I'm not mistaken, here are the details. In the originally setting of Almkist's trick, we show that $(\sum_{i=1}T_{ii})^{n(n-1)+1}$ is a linear combination of the $\phi_{n;i,j}$ as follows: 
Note that if $e_1,\ldots,e_n$ is the standard basis of $\mathbb{C}^n$, then
\begin{equation}
(\sum_{i=1}T_{ii})\det(e_1,\ldots,e_n) = \sum_{k=1}^n \det(e_1,\ldots,Te_k,\ldots,e_n).
\end{equation}
By multilinearity, for any vectors $b_1,\ldots,b_n$ we have 
\begin{equation}
(\sum_{i=1}T_{ii})\det(b_1,\ldots,b_n) = \sum_{k=1}^n \det(b_1,\ldots,Tb_k,\ldots,b_n).
\end{equation}
In particular, for any natural number $N$ we have 
\begin{equation}
(\sum_{i=1}T_{ii})^N = \sum_{k_1 + \ldots + k_n=N} \frac{N!}{k_1!\ldots k_n!} \det(T^{k_1}e_1,\ldots,T^{k_n}e_n),
\end{equation}
where the sum is over nonnegative integers $k_1,\ldots,k_n$ adding to $N$. When $N \geq n(m-1)+1$, it is guaranteed that at least one of the $k_i$ will be $\geq m$, so that the quantity on the right-hand-side is a polynomial linear combination of $\phi_{m;i,j}$.

To generalise this method to the polynomials $p_k$, we begin by noting
\begin{equation}
p_k \det(e_1,\ldots,e_n) = \sum_{1 \leq i_1 < \ldots < i_k \leq n} \det(e_1,\ldots,Te_{i_1},\ldots,Te_{i_2},\ldots,Te_{i_k},\ldots,e_n),
\end{equation}
where we understand that between the dots we have $e_i$s. In particular, iterating like before, for any $N$ we have
\begin{equation}
p_k^N = \sum_{k_1+\ldots+k_N = kN} C_{N,k}(k_1,\ldots,k_n) \det(T^{k_1}e_1,\ldots,T^{k_n}e_n),
\end{equation}
where $C_{N,k}(k_1,\ldots,k_n)$ is the number of ways of putting balls into $n$ bins in $N$ rounds with $k_j$ balls in bin $j$ at time $N$, with the rule that on each round, we put $k$ balls into $k$ different bins. In any case, provided $kN \geq n(m-1)+1$, we are guaranteed to have some $k_i \geq m$ for each summand, and hence for such $N$, this formula expresses $p_k^N$ as a polynomial linear combination of $\{\phi_{n=m;i,j} \}$.

Note that as $k$ increases, we need only take smaller powers of $p_k$ (i.e. the $N_k^{\text{th}}$ power with $N_k$ the smallest integer greater than $(n(m-1)+1)/k$) to express $p_k^{N_k}$ in terms of $\phi_{m;i,j}$. This makes sense, as $p_k$ is a higher degree polynomial. In fact, $p_k^{N_k}$ has degree $n(m-1)+1+r(k)$, where $0 \leq r(k) < k$.

This method also gives us a (probably quite inefficient) way of expressing a power of $\phi_{m;i,j}$ in terms of the $\phi_{m';i',j'}$. Write $\phi_{m;i,j} = \sum_k \lambda_kp_k$, where $\lambda_k$ are polynomials. Then $\phi_{m;i,j}^{n(N-1)+1}$ is a polynomial in powers of $p_k$, which again by this pigeonhole style principle, has every monomial containing a power of a $p_k$ of at least $N$. Provided $kN \geq n(m'-1)+1$, this power can then be written as a polynomial linear combination of the $\phi_{m';i',j'}$.


  [1]: https://sites.math.rutgers.edu/~zeilberg/mamarim/mamarimhtml/gert.html