Take the back roads from carlisle to brampton, from here there's a lovely quiet road following the river Irthing to Gilsland. From here you can pick up route 68 through Wark Forest, there's a bothy here for an overnighter. Follow this until bellingham, where i'd pick up the reivers route back to Tynemouth. probably about 50% road 50% offroad.
There's also a new YHA at Housesteads if your looking for some comfort.