Try here www.dogsit.com/ for a dogsitter, although you'll need to be honest about the chewing habits of the dog because they may not want to take a dog into their home that would damage it.
Kennels you need to visit a few and get a feel for the place. Good kennels should have no problem with you looking around.
To answer some of your questions...
Will he stop being toilet trained if he has to 'go' on the run of his accomodation when no one is able to take him out? Obviously he won't be going into a garden several times a day as he is with us.
Not in my experience no. When I worked in kennels a lot of dogs held on for their walks, others only used the outside run, a few used inside when they were shut in overnight. If your dog is used to going through the night there's no reason why he shouldn't be able to at kennels. My own dog has been to kennels since he was 6 months old and it was never an issue.
Will he develop an entirely new wake/ sleep/ feed routine that'll make it really hard to return to the one I need him to be on now?
My dog always slots straight back into the usual routine when he comes home. Dogs for quite strong situational associations so he should be able to adapt quite easily between one routine in one place and another in a different place.
Won't he get very lonely in a kennel and run with say 2 to 3 visits only a day from strangers?
Not likely! He'll be surrounded by other dogs for a start. Much better company for a youngster than people. I can't speak for all kennels but I know where I worked young pups were lavished with attention. They quite often were allowed to come and spend time with the staff during lunchbreaks and were often the one to get fussed if there was a spare moment in the day. It's a busy environment with a lot going on. Even if the staff aren't directly with him they'll be round and about cleaning kennels or taking dogs for walks. It's not like he'd only see a person once or twice a day.
Won't he lose his training and develop stress behaviours like barking for ages (he rarely barks unless he needs to tell me he needs the toilet or for a v short while when unsure or excited about something)?
No. Barky dogs bark a lot in kennels, quiet dogs are quiet. Sometimes, like feed time or when other dogs are coming in and out, it can set a lot of them off barking but they quickly settle down again.
What if he has some unavoidable scary experiences at the boarding kennels, say with other dogs or strange noises - and then develops fears/ anxieties?
Life is full of unavoidable scary experiences but actually I'd think there would tend to be less of them in a kennels, which is a very controlled environment, than there would be out in the real world.
I do honestly and truly think it would be the best option for you. How are you ever going to be able to relax taking the dog to a house that it might destroy and you'll be faced with a bill for repairs. There's no danger of that kind of damage in a kennels. It will be good for him to experience it young because it will make it easier for him to go again as he gets older. It will give you an option for the future as well. Also you'll have room for some human luggage in the car!
In the meantime you really need to get his chewing issues sorted because if he wasn't destructive all of this would be so much easier for you.