Right on!! When you go, PM me and I can give you exact locations of where we camped if you want. We found some nice little places.
I didn't use 4x4 once. Depending on the speed you wish to go, any vehicle can make it. We even saw a Sprinter RV and quite a few cars. That being said, if you have AWD I'm sure it would be nice on the gravel. I left mine unlocked and was usually doing about 80kph on most of it and still was being passed by every pickup that came behind us. I only had one or two pucker moments!
They grade the highway religiously, we passed two or three a day, there are absolutely some soft spots and some potholes but they aren't the worst I've ever driven through. The worst part of the road is when you get to the coast of Labrador, it's (was) pavement. It's now swiss cheese and makes driving very unpleasant and slow. The road varies between fresh asphalt, perfect gravel, and FSR quality road, nothing a honda civic couldn't do.
I would go the cheap van route (or buy a Delica!) and just take your time on the road. The one time I thought I may need 4x4 was when I pulled off the highway onto an old staging point to set up camp. The ground was very soft, but there were other opportunities that I could have taken I'm sure.
Anyways, anything else just let me know!!!