Eleazar Goodenough, author of "Tear-Able Magic" (available on my site), does quite a bit of hat magic, including Hat Rings. But for the former newspaper hats, he uses giftwrap paper instead. If your routine is about taking a sheet of paper and turning it into a variety of hats (using origami techniques rather than gimmicked hats of the type he describes in "Tear-Able Magic") the giftwrap is a good colorful alternative. If you get your giftwrap paper from the Dollar Store, it can be a bit on the flimsy side, but it is cheap and easy to give away without flinching. It can also be themed for Birthdays, Seasons, and special occasions, or just plain colorful patterns that are non-specific.
Lu Brent's newspaper hat fold (often called the "Ali Bongo Growing Hat") is best made from no-tear Tyvec paper, as described in The Wizards' Journal #8.