Proving the existence of a risk neutral measure is the difficult part. Once its existence is established, a simple calculation of conditional expectations allows to go from a numeraire to any other.
Write $\beta$ for the cash numeraire and $Q_\beta$ the corresponding risk neutral measure. Let $N$ be a numeraire (so $N$ is a positive process and $N/\beta$ is $Q_\beta$ martingale). Define a new measure by
$$
\frac{dQ_N}{dQ_\beta}|_{\mathcal{F}_T} = \frac{N_T/\beta_T}{N_0/\beta_0}
$$
Then, for any $P$ s.t. $P/\beta$ is a $Q_\beta$ martingale
\begin{eqnarray}
\mathbb{E}^{Q_N}[ \frac{P_T}{N_T} | {\mathcal{F}_t} ] &=& \frac{\mathbb{E}^{Q_\beta}[ \frac{P_T}{N_T} \frac{N_T/\beta_T}{N_0/\beta_0} | {\mathcal{F}_t} ]}{\mathbb{E}^{Q_\beta}[ \frac{N_T/\beta_T}{N_0/\beta_0} | {\mathcal{F}_t} ]}
= \frac{\mathbb{E}^{Q_\beta}[ \frac{P_T}{\beta_T} | {\mathcal{F}_t} ]}{\mathbb{E}^{Q_\beta}[ \frac{N_T}{\beta_T} | {\mathcal{F}_t} ]} = \frac{\frac{P_t}{\beta_t} }{\frac{N_t}{\beta_t} } = \frac{P_t}{N_t}
\end{eqnarray}
So $P/N$ is a $Q_N$ martingale.
If you assume that you have a Brownian market:
$$
\frac{dN_t}{N_t} = r_t dt + \sigma^N_t dW_t^\beta
$$
$$
\frac{dP_t}{P_t} = r_t dt + \sigma^P_t dW_t^\beta
$$
$$
\frac{dQ_N}{dQ_\beta}|_{\mathcal{F}_T} = \frac{N_T/\beta_T}{N_0/\beta_0} = \exp\left(\int_0^T \sigma^N_t dW^\beta_t - \frac{1}{2} \int_0^T |\sigma^N_t|^2 dt \right)
$$
By Girsanov, under $Q_N$,
$$
dW^N_t = dW^\beta_t - \sigma^N_t dt
$$
is a Brownian motion and using Ito's lemma you can check that
$$
\frac{d(P_t/N_t)}{P_t/N_t} = (\sigma^P_t - \sigma^N_t)dW^N_t
$$
which also shows that it is a Brownian martingale under $Q_N$.