The solution is to run both ethernet and phone over the same existing cat-5 cable. Every wall jack becomes two jacks, one RJ-11 for phone and one RJ-45 for ethernet. This neat hack could save you a lot of money, as you only have to buy new wall plates and jacks rather than wall plates, jacks, and hundreds of feet of wire.
See how this works in the next step.
Disclaimer: I'm not sure if this is legal. The telephone company won't be pleased if you short your telephone wires together. However, if you do everything right, they won't care. Don't blame me if you shock yourself (unlikely), damage Ethernet devices (also unlikely), damage phones (not as unlikely), damage your house wiring (not too unlikely), or damage your fingers with knives (rather likely).
Step 1: Theory
Cat 5 cable and RJ-45 jacks have eight wires.
Ethernet uses two pairs (four wires), one for send and one for receive.
Telephones use two wires.
Therefore, you can run both ethernet and telephone over the same wire, and still have two wires left over.
In fact, you could run two Ethernet jacks from a single cat-5 cable, or four telephone lines (though I don't know why you would run multiple phone lines.)
This Instructable will focus on changing wall plates from one RJ-45 (Ethernet) jack into one RJ-45 and one RJ-11 (phone) jack.
Note that I have not done extensive testing with cross-talk between phone and ethernet, though I have seen no degradation in the quality of either when both are in use.
Also note that this procedure will not work with PoE (Power over Ethernet) devices. Nothing bad will happen, it just won't transmit power. See step 13 for a possibly unsafe way to keep your PoE and add phone service. Also, it will not work with gigabit ethernet-- gigabit ethernet uses all four pairs. It will work fine at 10/100 Mbps which is sufficient for most people.