After a little work I think I found an inductive proof:
Let $M$ be finitely generated by $n$ elements. We perform induction on $n$. If $n=1$, $M=\langle m\rangle$ and there is some $x\in I$ such that $xm=m$. Thus $1-x$ annihilates $M$.
Assume by induction that we proved the claim for some $n-1$ and suppose $$M = \langle m_1,\ldots,m_n \rangle.$$ Consider $N = M / \langle m_n \rangle$. It is generated by $n-1$ elements and satisfies $N=IN$, so there exists $x \in I$ such that $1+x$ annihilates $N$. Therefore $$(1+x)M \subset \langle m_n \rangle.$$ Since $m_n \in IM$, $$(1+x)m_n \in (1+x)IM = I(1+x)M \subset I\langle m_n \rangle.$$ Take $y\in I$ such that $(1+x)m_n = ym_n$. Then $(1+x-y)m_n = 0$ and $$(1+x)(1+x-y) \in 1+I$$ annihilates all $M$.
In fact, one can use the same method to replace the determinant trick entirely. Unfortunately the resulting polynomial has high degree.
Claim: Let $M$ be finitely generated and $\varphi:M \rightarrow M$ an $R$-module homomorphism satisfying $\varphi(M) \subset IM$ where $I$ is an ideal (possibly all $R$). Then $$\sum_{i=0}^{k-1} a_i \varphi^i + \varphi^k = 0$$ on $M$ for some $a_0,\ldots,a_{k-1} \in I$.
Proof: This is really the same as the previous proof, just replacing $\mathrm{id}_M$ by $\varphi$ in some places and keeping track of what this entails.
The case $M=\langle m \rangle$ is clear: $\varphi(m) = xm$ for some $x \in I$, so $\varphi - x = 0$ on $M$.
Assume by induction that we proved the claim for some $n-1$ and suppose $$M = \langle m_1,\ldots,m_n \rangle.$$ Consider $N = M / \langle \{\varphi^i (m_n)\}_{i\ge 0} \rangle$. It is generated by $n-1$ elements and satisfies $\varphi(N) \subset IN$. Hence there exists some polynomial $p(x)$ (monic, with all but the top coefficient in $I$) satisfying $p(\varphi) = 0$ on $N$. Therefore $$p(\varphi)(M) \subset \langle \{\varphi^i (m_n)\}_{ i\ge 0} \rangle.$$
In fact it suffices to take $$ \langle \{\varphi^i (m_n)\}_{0\le i \le k} \rangle,$$ where $k$ is some natural number (take a maximum over the powers needed for the elements $p(\varphi)(m_i),\ \ i \le n$.)
Since $\varphi^{k+1}(m_n) \in IM$, $$(p(\varphi))(\varphi^{k+1}(m_n)) \in p(\varphi)(IM) = I\cdot p(\varphi)(M) \subset I \langle \{\varphi^i (m_n)\}_{0\le i \le k} \rangle.$$
Take $y_0,\ldots,y_k \in I$ such that $q(\varphi) = \sum_{i=0}^k y_i \varphi^i$ satisfies $$p(\varphi)\circ\varphi^{k+1}(m_n) = q(\varphi)(m_n),$$ and then
since $p(\varphi)\circ\varphi^{k+1} - q(\varphi)$ is monic with all but the top coefficient in $I$, $$p(\varphi)\circ(p(\varphi)\circ\varphi^{k+1} - q(\varphi))$$ gives a polynomial of the required form: composition of polynomials of an endomorphism = multiplication of polynomials. So the induction step gives $$(p(z)^2 \cdot z^{k+1} - q(z)p(z))\restriction_{z=\varphi}$$ where $y \in I.$
(edit: thanks to Yakov Varshavsky for pointing out an error near the last step, where I mistakenly thought $q$ could be taken to be a single monomial.)
