If you go to the link I posted upthread you see see my coast & castle rides on strava links
South Shields was Annies Guest House (bike storage in their yard covered by a tarp, take a big lock just in case. Very cheap and good value!)
Alnwick was the Youth Hostel (Bike storage in a secure bike shed, seemed a bit like a kids play room combined with a travel lodge, quite noisy!)
Berwick was The Kings Arms Hotel (bike storage was requested and they provided a meeting room for my bike, Italian next door was very good!)
This was the place I used, in Innerleithen. It was fantastic!
http://www.gledeknowe.co.uk/
I think I booked all of them apart from YH through booking.com iirc