...new telephone wire and ethernet cable without plugs to it and try pulling it throught the house

Won't work. Tried that. The telephone cable vanishes into the depths of the walls too thoroughly for that to work.

We also tried threading the cable through the front wall, along with the cable TV, but without success. This is why I purchased a drill.

Another thing is can you get under the floor to run cables under the house

Not easily, the living room floor is wood-panel, so lifting it is likely to be tricky.

You can see the walls (including the coving) in this photo: http://www.riocar.org/modules.php?set_albumName=album42&id=aaa&op=modload&name=gallery&file=index&include=view_photo.php

You can't see the floor in this one, but maybe I'll take more pictures later.

...if you are cohabiting with a woman convince her that you need to redecorate...

Well, I share the house with Toby (prolux), and persuading him that we need to redecorate wouldn't be hard. The landlord, on the other hand...