I may or may not have mentioned this to you once. I did the Long Range traverse in Gros Morne NP, though quite a few years ago. Essentially it was a 3 1/2 day bushwhack of c. 22 miles or so. Started with a commercial boat ride of Western Brook Pond. We were let off at the far end, and the rest of the day was spent climbing out of the fjord. From there it was all bushwhack to the Ferry Gulch trail, where we climbed up Gros Morne Mt., and then out to our spotted car. Bugs, mud, fog, and "tuckamore" (short balsam and fir that grows very thick) were the major obstacles. A true fantasy land of mountainous terrain, bogs, forests, streams, water falls, moose, caribou herds, and bear.
The ranger gave everyone a "grilling" checked our gear, wrote down colors (in case of a search), and we had to watch a short film. I think they now require each group to carry an electronic device for rescue. I think they said they give you 5 days before they start to worry about you.
I'm sure others on the forum have been there more recently than I.
I haven't done the North Rim, but I think it's a shorter trek. Someone I know did it a year or two ago, and I could put her in touch with you.
Lots of other hiking in and outside of GMNP as well, and I'm told that L'Anse aux Meadows is worth a side trip, if you have the time (we didn't).