I think your idea of Changbaishan is a good one - when I first started reading your post, I was thinking Changbaishan would be a good fit for hiking, and it also is a very different part of China from those you've been to. I've never actually made my way out to Changbaishan, but there are other places in the region that are much less touristed and worth visiting - I spent about a week in Huanren in eastern Liaoning back in 2004, and absolutely loved it.