When no solution exists, how do you satisfy as many constraints as possible? Suppose there exists no $x$ such that $Ax=b$. How would you go about choosing $x$ to maximize $|\{i : A_i x = b_i \}|$?

My first hunch would be to create a Mixed Integer Programming model:
$$\begin{array}{ll}
\min & \sum_i y_i \\
    & -My_i \le  \sum_j a_{i,j} x_j-b_i \le My_i \\
    & y_i \in \{0,1\} \\
\end{array}
$$
where $M$ is a large enough constant. There are some other tools developed to help diagnose infeasible Linear Programming models, such as IIS (Irreducable Infeasible Set).
See also the book John W. Chinneck: Feasibility and Infeasibility in Optimization. 
In a different answer it is suggested to add a positive slack to each equation and then minimize the sum of the slacks. This is related but I think not the same. The first thing we should notice is that we need to allow positive and negative slacks. We then can either minimize the absolute values or the squared values. I.e.:
$$\begin{array}{ll}
\min & \sum_i |s_i| \\
    & Ax = b + s \\
\end{array}
$$
or
$$\begin{array}{ll}
\min & \sum_i s^2_i \\
    & Ax = b + s \\
\end{array}
$$
The latter is of course just ordinary least squares. Besides this technical issue there is a more fundamental difference. When minimizing slacks we minimize the sum of of the infeasibilities. This is very different from minimizing the number of infeasibilities. Minimizing the sum of the infeasibilities may lead to a large number of small infeasibilities. In my MIP formulation we explicitly minimize the number of the infeasibilities.
In a reaction we see two objections made to the MIP formulations:


*

*How to choose $M$. This is valid point. We need in advance an upper bound on the maximum infeasibility we expect. This is a major drawback.

*This method would not flag things exactly. The concept of exactness is somewhat difficult when solving a system of linear equations. At least in LP/MIP solvers there are a large number of tolerances involved. But even a straight equation solver will not find exact solutions unless very special techniques are used. I don't think the MIP approach adds much "inexactness". 

