I know that the IRR can be computed using iterative methods, but why is this necessary? What makes it impossible to give an expression for IRR? How would you prove it to be impossible?
From the Wikipedia article, solving for the IRR is the same as finding a solution to an arbitrary polynomial. In general, it is difficult to solve an arbitrary $n$-degree polynomial with $n>4$.
I'm sure, given specific cash flow values and NPV, you can come up with explicit solutions for $r$, but general polynomials require more complicated formula than just taking roots.
Most of what is known about the difficulty of solving polynomial equations is covered in the field of Galois theory.