How difficult would it be to change the cable routing and run them under the bottom bracket and along the chain stay....I have no idea what it takes to braze on new cable guides so this is an honestly innocent question.
As a hobbyist framebuilder I've brazed a lot of cable guides (and brake bosses, bottle bosses, rack bosses, pump pegs, etc) onto original and existing frames for myself and others. It isn't difficult. Basic procedure is to remove paint under where the guide will go, flux the tube and fitting, locate the boss or guide with a small fixture if needed so it won't shift, evenly/minimally heat the joint between the two and flow the silver (or brass), then use emery cloth to clean up the charred paint (about 1cm each side, minimum), prime and spot-paint or respray.
If the frame will be resprayed, then it is worthwhile to minimally heat the old, unneeded cable guides so they can be picked off/removed for a neat and tidy appearance. Alternatively, some guides are minimal enough to remove with a few careful strokes of a file, cleaning up with production/emery cloth. I've sometimes removed them with a dynafile (a small portable handheld belt sander with a 13mm/0.5in belt).
As for cost, many framebuilders I know will take on a small project like this for a reasonable fee
per braze-on ($5 back in the day but now typically around $25 here in the US) if that's all you need. This pricelist is typical in my experience:
http://www.bantambicycles.com/repairs-and-retrofitsOn the old 1970 roadracing frame I employed for my Fixie, I decided to remain consistent with the age and ethos of the bike and use clamp-on cable housing guides (which I carved myself from stainless sheet) for my top tube-routed rear brake cable instead of brazing them on. Clamps aren't hard to make and that is another possibility.
Best,
Dan.