A dog that exclusively chews toys probably won't do well with stuffed anything - those kinds of toys aren't meant for unsupervised play.

However, anything made of thick rubber like the ones that Kong makes are my go-to. My dogs (a Boxer and an Australian Shepherd) are both chewers, and for them I specifically got rubber rings and "tires" made for dogs.