Reviving this thread because I can and have too much time to spare. Some nicknames I've come across in fanfiction:
- Roushi the Volcano
- Han the Burning Haze
- The Fourth Kazekage, the Golden Storm
- Unruly A
- Baki the Desert Tempest/Tempest Blade
- Gai and Lee, the Viridian Beasts of Konoha
- Samui, Omoi and Karui, the Three Storms of Kumo
- Itachi, the Raven of Konoha
- Kirabi of the Seven Swords
And some I came up with:
- Naruto the Golden Sage
- The Third Raikage, Strongest of Kumo
- Orochimaru, the White Snake of Konoha
- The Second Mizukage, the Troll of Kiri.
- Blood Prophet Hidan
- Heartless Kakuzu
- Tobirama the Heretic
- Konan the Origami Angel
- Mad Bomber Deidara
- Yagura the Ocean Shaker
- Yugito the Hellcat
- Kitsuchi of the Mountain
- Rubber Man Dodai
- Storm Cloud Darui
- Obito the Drifter
- Mei the Corrosion Queen
- Utakata of the Rot
- Quicklime Kurotsuchi
- Necromancer Kabuto
- Chiyo of the White Theater
- Weeping Yahiko
- All Seeing Ao
- Kankurou of the Black Cloth
- Demon Eyes Sasuke
- Mind Bender Ino
- Winter Prince Haku
- Bone Reaper Kimimaro
- Shadow Stalker Shikamaru
- Sakura of the Wild Cherry Blossoms