There's plenty of backpacking to be found up in the Bay of Islands, you could go hiking out to Cape Brett (couple day walk), then just make your way up north towards Cape Reinga. You'd probably have to walk on roads though, at least for some part.
You can get as adventurous as you like in the South Island, just get a good map, tell someone when you should be back, and head off.
