Conceptual question on eigenvectors in quantum mechanics

The word "span" is meant in a slightly different way than in elementary linear algebra, where (as you say) it wouldn't make sense for a set of vectors to span a space without actually being in it. As mentioned in the comment by Charlie, this requires the notion of rigged Hilbert spaces to actually formalize.

If you want the end-user result, it turns out that you can define the symbol $|x\rangle$ to have the following properties:

1. $\hat X|x\rangle = x|x\rangle$, so $|x\rangle$ acts like an eigenvector of the position operator with eigenvalue $x$, and
2. $\int_{-\infty}^\infty dx\ |x\rangle\langle x| = \mathbb 1$ is the identity operator

If you do this, then any state $|\psi\rangle$ can be expressed as $$|\psi\rangle = \mathbb 1 |\psi\rangle = \int_{-\infty}^\infty dx \langle x|\psi\rangle |x\rangle \equiv \int_{-\infty}^\infty dx \ \psi(x) |x\rangle$$ where $\psi(x)$ acts as the position-space probability amplitude for the state $|\psi\rangle$. Other properties also follow, such as the fact that $\langle x|y\rangle = \delta(x-y)$.

If you restrict yourself to following these rules, then all will be well. Note that we have not made any claims as to what $|x\rangle$ actually is - we haven't said it's an element of the Hilbert space (it isn't) - we are treating it as a purely formal mathematical symbol.

---

Justifying the existence of such an object more rigorously takes some work. What we first do is identify a special, extremely well-behaved subspace $S\subset \mathcal H$ of our Hilbert space. The defining characteristic of $S$ is that any vector $\phi\in S$ can be acted on by $\hat X$ and $\hat P$ as many times as you want without leaving $\mathcal H$. This is a very special property, which is not shared by most vectors in $\mathcal H$; it does turn out, however, that $S$ is dense in $\mathcal H$.

We then consider the set of all linear maps from $S$ to $\mathbb C$. This is called the (algebraic) dual space $S^*$. For example, let $\psi\in L^2(\mathbb R)$. The following are ways we could linearly map $\psi$ to $\mathbb C$:

1. $\psi \mapsto \psi(x)$ (we could evaluate it at a point)
2. $\psi \mapsto -i\psi'(x)$ (we could differentiate it, evaluate it at a point, and then multiply it by $-i$)
3. $\psi \mapsto \langle \phi|\psi\rangle$ (given any $\phi\in L^2(\mathbb R)$, we can take the inner product of it with $\psi$)

Convince yourself that these are all linear maps from $S$ to $\mathbb C$. The last example demonstrates that every element of the Hilbert space can be thought of as an element of $S^*$ (more properly, every element of $\mathcal H$ corresponds to an element of $S^*$, but nevermind that). However, the first two actions cannot be expressed as the inner product of some element of $\mathcal H$ with $\psi$, so it seems that $S^*$ is even larger. That's why you often see $S\subset \mathcal H \subset S^*$.

If you look at example (1) above, that looks an awful lot like $\langle x |\psi\rangle = \psi(x)$, and indeed this is the case. $\langle x |$ is an element of $S^*$, the algebraic dual space to $S$. More generally, $S^*$ corresponds to the space of "bra vectors", whereas the kets are elements of the nearly-identically-constructed antidual space $S^\times$, consisting of the conjugate linear maps from $S$ to $\mathbb C$.

That's a (hopefully gentle) introduction to the idea of a rigged Hilbert space. The answer linked in Charlie's comment gives a more thorough description, and for a real understanding you can read this wonderful paper by Rafael de la Madrid.

There is already a good answer from J. Murray. Here we merely want to answer OP's last question.

How can vectors not be a part of a vector space but still span it?

Answer: E.g. a basis $(\vec{e}_1,\ldots,\vec{e}_n)$ of a finite-dimensional vector space $V$ spans by definition $V$ and therefore a subspace $U\subset V$ even if none of the basis vectors belong to $U$.