Make the $ that opens a math environment replace preceding spaces with a single non-breakable?

Here's an example using the active characters approach. I'm not against this sort of idea for your own documents, but do note that it's probably not the most robust approach (like Martin comments, this could affect the inner workings of other packages—doing it \AtBeginDocument is probably a good idea).

\documentclass{article}
\makeatletter
\let\mathshift=$
\catcode`\$=\active
\protected\def$#1${%
  \ifdim\lastskip>\z@ \unskip\textvisiblespace \fi
  \mathshift #1\mathshift
}
\DeclareRobustCommand\({% from fixltx2e
  \ifdim\lastskip>\z@ \unskip\textvisiblespace \fi
  \ifmmode \@badmath \else \mathshift\fi
}
\makeatother
\begin{document}
\tableofcontents
\section{Introduction} Hello $a+b$
\section{Not sure $x=y$. $x=z$ though!}
And \( f(x) = x^2 \) too.

We'd better ensure no space gets added if there's nothing before the maths:
\begin{tabular}{|c|c|}
\hline
$a$ & $b$ \\
$c$ & $d$ \\
\hline
\end{tabular}
\end{document}

In order to make the example actually show the idea, I've used a visible space instead of a hard space. Remove \textvisiblespace above with ~ for your actual work :)

Also, I've assumed above that you're not using $$...$$ for display math, as strictly speaking it's not valid LaTeX syntax.

One way for not breaking other people's packages is to rely on the fact that package writers tend to be conservative, and adhere to ASCII. So, I would redefine the same set of macros that Will did, but have these parameterized by the math character, which can default, or not default, to $.

I am clueless as to how one can do this, but just imagine you could write

\usepackage[begin=〈, end=〉]{nbsm}

and then proceed, wrapping your inlined math with 〈 and 〉. Or if you are the daring type,

\usepackage[begin=$, end=$]{nbsm}