Why are there nine regular polyhedra? Context for question:
The study of polyhedra and more generally of polytopes has never been particularly focused on rigor, and many references for results are often either non-existent, or impossible to find.
This lead me to try to prove some basic results on polyhedra. To be clear, the definition of polyhedra I use is a set of polygonal faces and edges such that two faces are adjacent to each edge, no two elements coincide and such that no subset of faces and edges forms a valid polyhedron (this excludes compounds).
The problem with answering the question:
With this in mind, I can now use the common definition of a regular polyhedron as a vertex-transitive polyhedron with congruent, regular faces. However, I ran into a problem when trying to prove that there were only 5 convex and 4 non-convex types (Platonic and Kepler-Poinsot solids):
First of all, the common proof for the Platonic solids (the one that uses the fact that you can't have many shapes with many sides around a vertex) assumes too many things. For example, one first needs to prove that the sum of the angles around a vertex is less than $2\pi$, which is false in the general, not-necessarily-convex case. Also, one needs to prove that given a vertex arrangement, there's at most one regular polyhedron that can be made. And even with all of this, the argument can't be generalized to non-convex solids: One can fit perfectly 7 equilateral triangles around a vertex, if you allow them to intersect.
So, why are there only 9 regular types of polyhedra?
[EDIT #1]
Using Arentino's answer, I can immediately characterize the convex cases. If I could prove that the convex hull of any regular solid is regular, I could easily just check for polygons on the vertices of these five solids and check how to connect them to create the other four cases. However, I don't know why should this be the case either, and I have no idea of how to prove it.
[EDIT #2]
Assuming all "known" properties of convex hulls (they are polyhedra for finite sets of points, etc.), I have been able to prove that the convex hulls have to be vertex-transitive (any symmetry of the original polyhedron that takes vertex A to B, will preserve the positions of the vertices as a whole and therefore the convex hull. As a consequence, the vertex figures are all congruent. However, I still need to prove that the faces are all congruent and regular, and I don't know how to do this. (Yet again).
[EDIT #3]
At last, some useful literature! I found the following book (p. 260) where it describes why every Kepler-Poinsot solid must be a stellation of a regular polyhedron. (Although if someone can prove the thing about convex hills, I'd appreciate it deeply). There's just a tiny problem. I don't understand the proof completely. For example, why should the "kernel" of the polyhedron be a convex polyhedron? And even if it is, how did he show it consisted of regular faces?
 A: I don't know if what follows can be extended to non-convex polyhedra, but one can show that only five convex polyhedra exist by using Euler's formula.
Let $F$, $V$ and $E$ be the number of faces, vertices and edges in a regular polyhedron. Let every face have $n$ sides ($n\ge3$) and $k$ edges meet at every vertex ($k\ge3$). We have then: $E=nF/2$ and $E=kV/2$. Inserting these into Euler's formula $F+V-E=2$ gives:
$$
E={2nk\over 2n+2k-nk}.
$$
But this is a positive integer only if the denominator is $\ge1$, which gives:
$$
k\le2+{3\over n-2}.
$$
For $n=3$ we then get $k\le5$, that is $k=3$, $k=4$ or $k=5$; for $n=4$ we get $k\le7/2$, that is $k=3$; for $n=5$ we get $k\le3$, that is $k=3$. For $n\ge6$ we would have $k<3$, which is not allowed. So we have only the five possible values of $n$ and $k$ listed above.
If some kind of Euler formula also holds for non-convex polyhedra, then one could try to repeat this reasoning even in that case.
A: Sorry for not uploading this answer earlier. This came to me about a week ago as I tried to understand the (kind of incomplete) proof that I gave above. 
An $n$-fold rotation axis will be an axis of rotation that leaves the whole polyhedron invariant after rotating $\frac{2\pi}{n}$ over it. My solution depends basically on this lemma:
Lemma: A regular polyhedron $\{\frac{p}{a}, \frac{q}{b}\}$ has a $p$-fold rotation axis about a face that leaves it invariant, and a $q$-fold rotation axis about a vertex. (If you don't understand what I mean, look here).
Proof: Notice that given the numbers $\frac{p}{a}$ and $\frac{q}{b}$, given a face $\{p\}$ and an orientation of it (one of the two sides of such face), one can construct (at most) uniquely the regular polyhedra $\{p,q\}$. (This can be justified rigorously by proving that the pyramid that is formed by a vertex and the adjacent vertices is unique, which isn't that hard). Therefore, any symmetry of $\{p\}$ which doesn't move one side to the other must be a symmetry of the whole polyhedron, implying it has a $p$-fold symmetry axis through this face.
To check that it must also have a $q$-fold symmetry axis through a vertex, it is enough to check the dual. $\blacksquare$

 Ok, I lied, it's not that simple. Because doing this assumes the dual of a regular polyhedron is regular. However, if we prove that a polyhedron is regular iff it is vertex, edge and face-transitive, we'll be done. To prove the "if" part, we just need to note that face and edge-transitivity imply that all faces are congruent and regular, in that order. (All sides equal implies regular here because since a regular polyhedron's vertices lie in a sphere, their faces must be cyclic. To prove that the vertices lie on a sphere in the first place, it's enough to use facts about symmetry groups). To prove the "only if" part, we just need to apply the above lemma repeatedly, since it's very easy to prove that there is a symmetry mapping two adjacent edges or faces one to another.

Ok, now comes the slick part. Since a regular polyhedron clearly can't have a $C_n$ or $D_n$ rotation group, since by our lemma we must have at least 2 $n$-fold axis that leave the figure invariant (with $n\geq 3$). But neither the tetrahedral, octahedral nor the icosahedral rotation groups contain rotations of order greater than 5. Therefore, in a $\{\frac{p}{a},\frac{q}{b}\}$, $p,q\leq 5$. That is, $\frac{p}{a}, \frac{q}{b}\in\{3,4,5,\frac{5}{2}\}$. This leaves very few cases that may be checked by hand. (And with a further bit of help from rotation groups again).
The proof that I had sent is also valid, but assumes implicitly that a regular polyhedron is both face and edge-transitive.
A: In fact it indeed depends on context, cf. the following video on the nowadays proven 48 regular polyhedra
