What's the best solver that can solve a large sparse but indefinite matrix?
You may want to watch lecture 34 here: http://www.math.tamu.edu/~bangerth/videos.html
Prof. Bangerth's lecture has already covered most of it, but I'd recommend you look at this paper. The authors take three of the most common methods (GMRES, CGS and CGNE) and give some matrices for which one method will converge in O(1) operations and the other two converge in O(N). The upshot of this is that there is no uniformly best iterative method for indefinite systems.
There are some special cases. For example, if your matrix is symmetric but indefinite, you'll want to use MINRES, or if your matrix comes from a constrained optimization problem there's a family of methods based on the Uzawa algorithm that you'd want to look at. Nonetheless, no one method works best for everything.
All told, you'll be better off asking what's the best preconditioner for the specific problem you have in mind. Prof. Bangerth has a bunch of lectures on this topic already, but I'll mention ILU as a fairly popular approach which works for a lot of problems and is pretty easy to understand (if not to analyze).
The question cannot be answered in this generality. It depends on the system. If it is related to the discretization of partial differential equations, a well designed multigrid method is of linear complexity. It can be used as a preconditioner in a Krylov-space method for additional robustness.