Proof of $|C_{G/N}(gN)| \leq |C_G(g)|$ without character theory In the book Character Theory of Finite Groups by Isaacs the following is proven (Corollary 2.24) using character theory:

Proposition: Let $G$ be a finite group and $N \trianglelefteq G$. Then $|C_{G/N}(gN)| \leq |C_G(g)|$ for all $g \in G$.

Isaacs mentions that "The following could be proved without characters but it is somewhat tricky to do so".  
So what is a character-free proof for the above proposition? 
I know how to do this in a special case. If $g$ has order coprime to $N$, then it is possible to prove (the proof I know is a bit long) that $C_{G/N}(gN) = C_G(g)N/N$. Then $$|C_{G/N}(gN)| = |C_G(g)N/N| = |C_G(g) / N \cap C_G(g)| \leq |C_G(g)|$$
 A: $\newcommand{\Size}[1]{\lvert #1 \rvert}\newcommand{\Set}[1]{\{ #1 \}}$Consider the actions of $G$ and $G/N$ by conjugacy on themselves, and write $x^{y} = y^{-1} x y$, and $x^{G} = \{ x^{y} : y \in G \}$.
We have 
$$
\Size{G} = \Size{g^{G}} \cdot \Size{C_{G}(g)}
$$
and
$$
\frac{\Size{G}}{\Size{N}} = \Size{G/N} = \Size{(gN)^{G/N}} \cdot \Size{C_{G/N}(gN)}.
$$
Now note that 
$$(gN)^{G/N} = \Set{gN^{yN} : y \in G} = \Set{g^{y} N : y \in G} = g^{G} N,$$
 so that we get the key inequality $$\Size{g^{G}} \le \Size{N} \cdot \Size{(gN)^{G/N}},\tag{key}$$ because $g^{G}$ is contained in the union of the cosets that make up $(gN)^{G/N}$.
In other words (since this is the key point), the map $f : g^{G} \to (gN)^{G/N}$ that sends $g^{y} \to g^{y} N = (gN)^{yN}$ is surjective, and we have for the pre-image of a point $f^{-1} (g^y N) \subseteq g^{y} N = \Set{g^{y} n : n \in N}$, so that we get (key).
It follows that
\begin{align}
\Size{gN^{G/N}} \cdot \Size{C_{G/N}(gN)} &= \frac{\Size{G}}{\Size{N}} 
= \frac{\Size{g^{G}} \cdot \Size{C_{G}(g)}}{\Size{N}} 
\\&\le
\frac{\Size{N} \cdot \Size{(gN)^{G/N}} \cdot  \Size{C_{G}(g)}}{\Size{N}}
\\&\le \Size{(gN)^{G/N}} \cdot  \Size{C_{G}(g)},
\end{align}
form which one gets
$$
\Size{C_{G/N}(gN)} \le \Size{C_{G}(g)}.
$$
A: Here's a proof I'm especially proud of:
For $g\in G$, let $C_G^N(g)=\{x\in G | [x,g]=xgx^{-1}g^{-1}\in N\}$.
In other words, $C_G^N(g)$ is the set of elements in $G$ which commute with $g$ "up to" an element in $N$. Note that:
$x\in C_G^N(g) \iff xN\in C_{G/N}(gN)$
so $C_G^N(g)$ is actually a subgroup of $G$ which contains both $C_G(g)$ and $N$, and $C_{G/N}(gN)=C_G^N(g)/N$.
Now, consider the function $f : C_G^N(g) \rightarrow N$ defined by:
$f(x)=[x,g]$
If $f(x)=f(y)$, then:
$[x,g]=[y,g]$
$xgx^{-1}g^{-1}=ygy^{-1}g^{-1}$
Cancelling the $g^{-1}$ on the right and rearranging,
$(y^{-1}x)g(y^{-1}x)^{-1}=g$.
So this means $f(x)=f(y)$ if and only if $y^{-1}x \in C_G(g)$. Or, put another way, $f$ is constant on cosets of $C_G(g)$ in $C_G^N(g)$.
The number of different values that $f$ takes is then just the number of cosets of $C_G(g)$ in $C_G^N(g)$. But recall also that $f(x)=[x,g]$ is a function with values in $N$. This means that:
$\text{Number of cosets of }C_G(g)\text{in }C_G^N(g) \leq |N|$
$\frac{|C_G^N(g)|}{|C_G(g)|}\leq |N|$
$\frac{|C_G^N(g)|}{|N|}\leq |C_G(g)|$
$|C_{G/N}(gN)|\leq |C_G(g)|$
