My fiancé and I hiked the Wall last year. We took 9 days and walked the entire way, and we did a series of blog posts about it. I can't recommend this journey enough, it was amazing!
We were roughly following the trail laid out in the best book we could find on the path, which breaks it into 9 sections, and has tips on lodging and food at nearly every place along the way. Start your research here.
This is a pretty popular walk for Britons, so there are accommodations of all sorts all along the walk, from primitive camping to luxury hotels.
You could potentially park your car somewhere in Newcastle or Carlisle, and take the train or a bus back there on your last day. I don't know of any specific places, but both are sizable cities, and there should be safe parking near the train stations.
The absolute best parts of the wall are to be found near the Crags, right in the middle of the walk. The scenery is breathtaking, and this is a remote enough area that the stones weren't cannibalized for building castles and churches in the middle ages. Vindolanda is also near there, and it's both a well-funded museum of all things Roman and a live archaeological dig.