A proof that you need at least 5 qubits (or qudits)
Here is a proof that any single-error correcting (i.e., distance 3) quantum error correcting code has at least 5 qubits. In fact, this generalises to qudits of any dimension $d$, and any quantum error correcting code protecting one or more qudits of dimension $d$.
(As Felix Huber notes, the original proof that you require at least 5 qubits is due to the Knill--Laflamme article [arXiv:quant-ph/9604034] which set out the Knill--Laflamme conditions: the following is the proof technique which is more commonly used nowadays.)
Any quantum error correcting code which can correct $t$ unknown errors, can also correct up to $2t$ erasure errors (where we simply lose some qubit, or it becomes completely depolarised, or similar) if the locations of the erased qubits are known. [1, Sec. III A]*. Slightly more generally, a quantum error correcting code of distance $d$ can tolerate $d-1$ erasure errors. For example, while the $[\![4,2,2]\!]$ code can't correct any errors at all, in essence because it can tell an error has happened (and even which type of error) but not which qubit it has happened to, that same code can protect against a single erasure error (because by hypothesis we know precisely where the error occurs in this case).
It follows that any quantum error correcting code which can tolerate one Pauli error, can recover from the loss of two qubits. Now: suppose you have a quantum error correcting code on $n \geqslant 2$ qubits, encoding one qubit against single-qubit errors. Suppose that you give $n-2$ qubits to Alice, and $2$ qubits to Bob: then Alice should be able to recover the original encoded state. If $n<5$, then $2 \geqslant n-2$, so that Bob should also be able to recover the original encoded state — thereby obtaining a clone of Alice's state. As this is ruled out by the No Cloning Theorem, it follows that we must have $n \geqslant 5$ instead.
On correcting erasure errors
* The earliest reference I found for this is
Grassl, Beth, and Pellizzari.
Codes for the Quantum Erasure Channel.
Phys. Rev. A 56 (pp. 33–38), 1997.
— which is not much long after the Knill–Laflamme conditions were described in [arXiv:quant-ph/9604034] and so plausibly the original proof of the connection between code distance and erasure errors. The outline is as follows, and applies to error correcting codes of distance $d$ (and applies equally well to qudits of any dimension in place of qubits, using generalised Pauli operators).
The loss of $d-1$ qubits can be modelled by those qubits being subject to the completely depolarising channel, which in turn can be modeled by those qubits being subject to uniformly random Pauli errors.
If the locations of those $d-1$ qubits were unknown, this would be fatal. However, as their locations are known, any pair Pauli errors on $d-1$ qubits can be distinguished from one another, by appeal to the Knill-Laflamme conditions.
Therefore, by substituting the erased qubits with qubits in the maximally mixed state and testing for Pauli errors on those $d-1$ qubits specificaly (requiring a different correction procedure than you would use for correcting arbitrary Pauli errors, mind you), you can recover the original state.