It's even simpler. Let's work in the position representation, i.e., using the generalized position eigenbasis. It's "generalized", because the spectrum of the position operator is continuous (the entire real axis) und thus there don't exist true eigenvectors but only generalized ones, i.e., they are not Hilbert-space vectors but distributions on a larger dual space; look for the concept of "rigged Hilbert spaces" as the modern way to formalize this mathematically. As physicists we just use the whole thing very naively as follows: For this first approach let's assume that we already know that the momentum operator in the position space reads
$$\hat{p}=-\mathrm{i} \partial_x,$$
where I've set ##\hbar=1## ("natural units") to simplify the notation as much as possible. Then the generalized momentum eigenstates ##u_p(x)=\langle x|p \rangle## are defined by the eigenvalue problem
$$\hat{p} u_p(x)=-\mathrm{i} \partial_x u_p(x) \stackrel{!}{=} p u_p(x).$$
The general solution for the equation is
$$u_p(x)=n_p \exp(\mathrm{i} p x).$$
Of course, ##p## should be real, and only then the formalism makes sense because it just describes the transformation from the position to the momentum representation as a Fourier transform which is extendible to a unitary transformation on the entire Hilbert space of squareintegrable wave functions.
Now we just need to find the normalization constant, but the state obviously is not normalizable, because it's not a square integrable function (for no value of ##p##), but we can "normalize it to a ##\delta## distribution" (sloppy phycisists' slang again), i.e., we want to normalize the momentum eigenstates as
$$\langle p|p' \rangle=\delta(p-p')$$
Now we translate this into the position picture by inserting a completeness relation,
$$\int_{\mathbb{R}} \mathrm{d} x \; |x \rangle \langle x|=\hat{1}.$$
This gives
$$\langle p | p' \rangle = \int_{\mathbb{R}} \mathrm{d} x \; \langle p|x \rangle \langle x|p' \rangle=\int_{\mathbb{R}} \mathrm{d} x \; u_p^*(x) u_{p'}(x) = n_p^* n_{p'} \int_{\mathbb{R}} \mathrm{d} x \; \exp[\mathrm{i} x(p'-p)]=2 \pi n_p^* n_{p'} \delta(p-p')=2 \pi |n_p|^2 \delta(p-p').$$
Thus, up to an unimportant phase we have
$$n_p=\frac{1}{\sqrt{2 \pi}} \; \Rightarrow \; u_p(x)=\frac{1}{\sqrt{2 \pi}}.$$
An arbitrary square-integrable wave function in position representation, ##\psi(x)=\langle x|\psi \rangle##, can thus be transformed to the momentum representation via
$$\tilde{\psi}(p)=\langle p|\psi \rangle = \int_{\mathbb{R}} \mathrm{d} x \langle p | x \rangle \langle x|\psi \rangle=\frac{1}{\sqrt{2 \pi}} \int_{\mathbb{R}} \mathrm{d} x \exp(-\mathrm{i} p x) \psi(x)$$
or in the other direction
$$\psi(x)=\langle x|\psi \rangle = \int_{\mathbb{R}} \mathrm{d} p \langle x|p \rangle \langle p|x \rangle=\frac{1}{\sqrt{2 \pi}} \int_{\mathbb{R}} \mathrm{d} p \exp(\mathrm{i} p x) \tilde{\psi}(p).$$
The remaining problem is to derive this result without using the position representation, i.e., in the representation-free Hilbert-space formalism. This only uses the Hilbert-space structure of quantum theory and the Heisenberg algebra for position and momentum,
$$[\hat{x},\hat{p}]=\mathrm{i} \hat{1}.$$
To this end we can use group theory to get an idea for the ansatz, how to solve this problem. The Heisenberg algebra implies that momentum generates translations in space. We don't really need this, however. So just take the following as a clever trick. The idea is to consider the operator
$$\hat{T}(\xi)=\exp(-\mathrm{i} \xi \hat{p})$$
and assume that there exists a (generalized) position eigenvector ##|x \rangle## for some ##x \in \mathbb{R}##. Now we like to show that also
$$|x' \rangle = \hat{T}(\xi) |x \rangle$$
is a position eigenvector. At the same time we like to figure out what the spectral value ##x'## might be. To that end we let the position operator act on this vector. Then it would be great to know, what's the commutator of ##\hat{x}## with ##\hat{T}(\xi)##, because then we could bring ##\hat{x}## to act on the ##|x \rangle##. So we first calculate this commutator. To that end we need the commutator of ##\hat{x}## with any integer power of ##\hat{p}##, because the operator exponential is defined by the corresponding Taylor series,
$$\hat{T}(\xi)=\sum_{k=0}^{\infty} \frac{1}{k!} (-\mathrm{i} \xi \hat{p})^k.$$
Thus for the commutator we need
$$\hat{C}_k=[\hat{x},p^k]=\hat{p}[\hat{x},\hat{p}^{k-1}]+[\hat{x},\hat{p}] \hat{p}^{k-1} = \hat{p} \hat{C}_{k-1} + \mathrm{i} \hat{p}^{k-1}.$$
This is a recursion relation for ##\hat{C}_k##. Starting from ##k=1## and the trivial relation ##\hat{C}_0=[\hat{x},\hat{1}]=0## leads to
$$\hat{C}_1=\mathrm{i}, \quad \hat{C}_2=\hat{p} \hat{C}_0+\mathrm{i} \hat{p}=2 \mathrm{i} \hat{p}, \quad \hat{C}_3 = \hat{p} \hat{C}_2+\mathrm{i} \hat{p}^2 = 3 \mathrm{i} \hat{p}^2,\ldots, \hat{C}_k=\mathrm{i} k \hat{p}^{k-1}.$$
This leads to
$$[\hat{x},\hat{T}(\xi)]=\sum_{k=1}^{\infty} \mathrm{i} k \frac{1}{k!} (-\mathrm{i} \xi)^k \hat{p}^{k-1}=\xi \sum_{k=1}^{\infty} \frac{1}{(k-1)!} (-\mathrm{i} \xi \hat{p})^{k-1}= \xi \hat{T}(\xi).$$
Thus we finally get
$$\hat{x} |x' \rangle=\hat{x} \hat{T}(\xi) |x \rangle=\left ([\hat{x},\hat{T}(\xi)]+\hat{T}(\xi) \hat{x} \right ) |x \rangle = (\xi+x) \hat{T}(\xi) |x \rangle.$$
This means that ##|x' \rangle## is eigenvector of ##\hat{x}## with the eigenvalue ##x'=x+\xi##. Thus, if the position operator has one real spectral value entire ##\mathbb{R}## is its spectrum. We thus can use the following generalized position eigenbasis
$$|x \rangle=\hat{T}(x) |x=0 \rangle.$$
From this you get
$$\langle p|x \rangle=\langle p|\hat{T}(x)|x=0 \rangle=\langle \hat{T}^{\dagger}(x) p|x=0 \rangle=\exp(\mathrm{i} x p) \langle p|x=0 \rangle=n_p \exp(\mathrm{i} x p).$$
Normalizing again to a ##\delta## distribution for the position eigenstates leads to ##n_p=1/\sqrt{2 \pi}## and leads again (up to an unimportant phase) back to
$$u_p^*(x)=\langle p|x \rangle=\frac{1}{\sqrt{2 \pi}} \exp(\mathrm{i} p x).$$