I always end up green with envy that people seem to have pre-existing conduits in their walls for running new cables. There's no way, in my old house, of doing this without some invasive smashing in to walls.
I had my house wired up with 30 Cat 6 drops (3 being in-ceiling for AP's) and in the end it was simpler to go up to the loft (2 story house) and come down that way, with all of the cables then being bundled up and coming down through a built-in-wardrobe into the garage below.
It required a bit of patching here and there where a small chase had to be chisseled out to get around a cable going through a patch of plaster used for dot and dab (technique to quickly plasterboard/drywall onto brick), but with conduit it would have been a much simpler job.