Jacobian-Free Newton-Krylov (JFNK) methods, and Krylov methods in general, can be very useful because they don't require explicit storage or construction of a matrix, only the results of matrix-vector products. If you do actually form the sparse system, there's many preconditioners out there for you.
What is available for true matrix-free methods? Googling turns up some references to "matrix estimation" and some other things indicating that it is possible. How do these methods generally work? How do they compare to traditional preconditioners? Are physics-based matrix-free preconditioners the way to go? Are there any openly available methods in the wild, say in PETSc or some other package?