You're not particularly spot on with your definition of electric flux. Most fundamentally, the electric flux $\Phi$ through a given surface $S$ is defined to be
$$
\Phi=\int_S \mathbf E\cdot\mathrm d \mathbf S.
$$
If you introduce a well-defined model in terms of field lines, then this does end up describing the number of field lines that cross $S$, to within the limits of the model. When the model is accurate, both share the same features: saying that $\Phi$ depends on the number of field lines instead of their density is the same as saying that $\Phi$ stays constant if we increase the decrease the line density and proportionally increase the surface area, and indeed the same is true if you decrease the electric field strength and proportionally increase the surface area.
The reason we define the electric flux is because it is useful. It is precisely the correct quantity to relate the electric field to the existing charges, and this is done via Gauss's law,
$$
\oint_S \mathbf E\cdot\mathrm d \mathbf S=\frac{1}{\epsilon_0}Q_\text{enc}.
$$
This is the fundamental law of electrostatics, really, and it all flows from here (and also the superposition principle). What else do you need for it to be physically meaningful?
Another misconception is to say that the electric flux
is not proportional to the relative density of field lines, which would supply information regarding the strength of the field at that point.
It cannot tell you anything about what happens at any given point because it's not a function of any point, it talks about what happens on a given surface as a whole. And, if you're given a space-dependent vector field and a surface, there's not really many invariant ways to combine them other than through the flux.
I am posting this because I believe none of the the other answers address the OP's question. The answer is already in the text by Feynman but somewhat implicitly.
We have a positive charge $q_+$ at the point $P_0$. We want to know if it is possible for $q_+$ to be in stable equilibrium.
Q: What do we mean by stable equilibrium?
A: A particle is in stable equilibrium happens at a point $P_0$ if it experiences no force at $P_0$ and if we make a small perturbation (i.e., we move the particle from the equilibrium point by a small distance) there is a force that makes it return towards the equilibrium point. Such a force is called a restoring force.
In electrostatics all forces can be expressed in terms of electric fields. A charge $q$ will experience a force
$$\overrightarrow {F_q} = q \overrightarrow E$$
For the particular case of our charge $q_+$ the force points towards the same side as the electric field.
We can now start with the assumption that $P_0$ is a point of stable equilibrium for $q_+$. This means that there is a restoring force in some neighborhood $V$ of $P_0$ inside of which, at every point $Q$, the electric field $\overrightarrow E$ points from $Q$ to $P_0$. If we apply Gauss's law to such a system we get
$$\oint\limits_{S=\partial V}\overrightarrow E\cdot\overrightarrow n ~\mathrm d a=\frac{q_+}{\varepsilon_0}$$
where $S$ is the boundary of the neighborhood $V$. But if we look at the left side of the equation we see that $\overrightarrow E$ points inwards whereas $\overrightarrow n$ points outwards (as per the convention for normal vectors to a closed surface). This means that the integrand is always negative and so the integral is as well.
A negative number cannot be equal to a positive number! Therefore, by reductio ad absurdum we conclude that $P_0$ cannot be an equilibrium point. Our starting assumption was wrong.
With the legwork we have done here we can also expand one of points Feynman makes. The text reads
except right on top of another charge
If there are several charges, and they are at different points in space we can always find a volume inside of which it is isolated and as we saw above, this can never be a point of stable equilibrium. But if two charges $q_1, q_2$ are right on top of one another then no matter how small a volume we take the right hand side of the equation will always be $(q_1+q_2)/\varepsilon_0$.
So, if our charge $q_+$ sits right on top of a negative charge $Q_-$, and $|Q_-|>q_+$, then is in stable equilibrium because Gauss's law does allow it this time (both sides are negative).
With this we can expand Feynman's claim to:
There are no points of stable equilibrium in any electrostatic field—except right on top of another charge of opposite sign and higher value.
Best Answer
Field lines draw all of their validity from Gauss's law for the electrostatic field, $$ \nabla\cdot \mathbf{E}=\frac1{\epsilon_0}\rho,\ \text{or equivalently}\ \oint_{\partial\Omega}\mathbf{E}\cdot\text d\mathbf{S}=\frac1{\epsilon_0}Q_\Omega, $$ where $Q_\Omega=\int_\Omega\rho\,\text d\mathbf{r}$ is the electric charge in a volume $\Omega$ whose surface is $\partial \Omega$, and the fact that it can be mapped exactly into the continuity equation for some fluid in the steady state, which states that $$ \nabla\cdot \mathbf{j}=\sigma,\ \text{or equivalently}\ \oint_{\partial\Omega}\mathbf{j}\cdot\text d\mathbf{S}=\Sigma_\Omega $$ where $\mathbf{j}$ is the current density (i.e. the amount of fluid that crosses a unit area per unit time, which is equal to the fluid density times the local velocity), $\sigma$ is the amount of fluid being created per unit time per unit volume, and $\Sigma_\Omega=\int_\Omega\sigma\,\text d\mathbf{r}$ is the total fluid created inside $\Omega$ per unit time.
The exactly identical form of these two equations means that we can fruitfully interpret the electric field as the velocity of a fictional "fluid", which is conserved or not depending on whether charges are present. More specifically, we can bring in a useful way of describing fluids - the use of streamline diagrams - to help us visualize electric fields (and, indeed, magnetostatic and gravitational fields, to which all of this post also applies).
Let's use, then, this mapping: we can map your question, "how and why do electric field line diagrams work?" into a corresponding question in the dual problem:
Streamline diagrams depict a finite number of lines which are tangential to the current $\mathbf{j}=\rho_\text{fluid}\mathbf{v}$ at all points. That means a particle that starts on a streamline will stay on it as the fluid flows.
The fun starts when streamlines suddenly get closer to each other. This means that either the fluid has been compressed, or that the unit volume of fluid has been stretched so it is longer along the streamlines (as in e.g. this diagram), and therefore the fluid is going faster. Either way, the fluid current density $|\mathbf{j}|$ increases.
This can be made more precise. In the image of the airfoil above, for example, the streamline 'seeds' (the points on the left at which the streamlines start) have been chosen so that the fluid flowing per unit time into the image from the left in between any two adjacent streamlines is constant. Because no fluid flows across a streamline, this rate of fluid flow must remain constant. Because of that, when the streamlines are closer together, the rate of fluid flow per unit area (i.e. the current density) is bigger.
(In addition to that, if there are sources or sinks where the fluid is created or destroyed, then you may need to introduce or remove some streamlines, because in such a situation the rate of fluid flow between the original streamlines is of course no longer conserved.)
Because of this fact, if you are given a pictorial representation of the streamlines of a fluid flow, then you can use it to reconstruct an approximation of its current density field. Its direction is given by the streamlines, and its magnitude is dictated by the spacing to the neighbouring streamlines. This is of course only approximate: you can try and interpolate the values between two streamlines, but you're missing information. You can try and improve your approximation by taking a finer grid, i.e. decreasing the flow rate needed to mark the next streamline, and that will give you better precision (but of course it will still be an approximation).
Conversely, to produce a streamline diagram you must first agree on the flow rate which should be taken until the next streamline. After that, you start off your "official" streamlines at one end of the flow, with the appropriate spacing, and you follow them through to the end. (Note, though, that because of the conservation of rate-of-flow-between-adjacent-streamlines, you can also start off your streamlines in the middle of the flow, as long as you space them appropriately). There will then be a finite number of "official" streamlines, as well as an infinite number of potential streamlines you could draw in between them. It is of course the "official" ones that you should use when estimating the current density from the diagram.
You can then make the spacing between "official" streamlines smaller, and it will get you a more accurate representation of the flow field. Even better, if your streamlines are really close together, it begins to make sense to speak of the local density of official streamlines. If the fluid slows down by a half from one region into another, and your streamlines are still very close together, then you'll find that there are twice as many in a given finite-and-small-ish area where the fluid is fast compared to where it is slow.
In the limit where you take infinitely many streamlines, equally spaced at a correspondingly vanishingly small flow rate, then you get the sort of thing that gets platonically talked about. It doesn't make sense, though, since you have to work at a finite spacing, but if your spacings are very small then you can both (1) have streamlines essentially through every point, and (2) speak meaningfully about the local density of official streamlines, and have that change consistently from one region to another depending on the local current density.
One useful tool to visualize this limit is Paul Falstad's 3-D Vector Fields Applet. For one, it lets you visualize electric fields as the velocity fields of fictitious particles, and it lets you play around in three dimensions with many of the standard electrostatics configurations, but most importantly it lets you increase and decrease the field line density:
It works exactly like this, too, in electrostatics. If you have an electrostatic field (or a gravitational field), then you start off by picking a suitably small unit of electrostatic flux (i.e. $\int_S\mathbf{E}\cdot\text d\mathbf{S}$ to separate your field lines. Once you fix this, the field line diagram is essentially completely determined: starting at a given point, you can draw its field line, then move off one unit of flux up and down from it and draw those field lines, and repeat that until you've covered all the region of interest. And, of course, if you meet regions with charges, then you need to thin down your streamline density or introduce some new ones. Gauss's law then guarantees that your diagram will be consistent: if you pick your spacings so that the local density of field lines reflects the electric field strength $|\mathbf{E}|$ across a given surface, then it will do that throughout the entire diagram. That is why you can use such a concept, and the reason it really works.
I would also like to set down here some thoughts on representation. Through the procedure I outlined above, it is indeed possible to reconstruct an approximation to the electric field in a region from a diagram with a finite number of field lines. Thus, these two representations of the same dipolar electric field are essentially equivalent*:
However, just because they contain the same information, it doesn't mean that they are equally useful. Field line diagrams are very useful for forming an intuitive idea of what direction the field points in and its relative strength in different regions, but it is a terrible tool for estimating the superposition of two fields (for which a vector field representation is better), and it creates several incorrect intuitions. At the end of the day, even though we can indeed 'explain the force of gravity from the field representation without using the mathematical equation', attempting to do so turns out to be absolutely not worth the trouble. You should really see the field lines as merely a representational tool, and stick to the mathematics of the vector field for 'what the field really is'.
Finally, let me make explicit here a warning. The language in this post is primarily suited for two-dimensional situations, and it needs to be slightly modified for 3D scenarios. The reason for this is that in three dimensions there is no "next streamline", and you need to start off with an appropriate spattering of points, with the correct local density, in your 'seed' surface when drawing field lines. The correct generalization of 2D streamlines to 3D is still streamlines, and not "streamsurfaces" (which you can indeed draw, but everything becomes a whole lot messier), and this complicates things. Nevertheless, it is indeed possible to do this properly, and the analogy between a static fluid flow and electrostatics remains.
In fact, this seemingly harmless 2D/3D divide can be the cause of many subtle mistakes. Take, for example, this common representation of the field lines of a point charge, from anupam's duplicate question:
For a point charge, it is the electric field flux through a sphere centred on the charge that is constant, which means that the electric field must go down as $1/r^2$. In this image, though (or in any 2D depiction in which field lines don't vanish), the spacing between the lines goes down as $1/r$ (since the number of field lines which cross a circle is constant), which means that it is seriously overestimating the field strength. This diagram is more suited for depicting the electric field of a line of charge.
Thus, to correctly estimate the field from such a diagram, you need to work from a 3D diagram like the ones produced by Paul Falstad's simulator, which produced the graphics above, ( or this one, if you have the cash), or you should work in 2D systems (i.e. 3D systems with a translational symmetry).
This sort of mistake, though, is exclusive to a field line representation - you wouldn't make it when using a vector field representation. You can use them to build some intuition, but beware of their many breakdowns and always complement them with other ways to visualize the fields.
* Note that if you directly attempt to plot this in Mathematica,
StreamPlotwill produce an incorrect plot, with field lines appearing out of nowhere; it is surprisingly hard to produce proper streamline plots both in Mathematica and elsewhere. For the code that produced this ones, use Import["http://goo.gl/NaH6rM"]["http://i.stack.imgur.com/CMlWz.png"]. Also, note that I cheated by reducing the contrast in the vector plot somewhat to make the arrows more visible.