That's why you want to bring your Grigori Medic promoted Flesh Golem with HN along for the ride. The two Shadows (not heroes, just regular Shadows promoted from some found Lizardmen) and the Flesh Golem ran rampant through several empires and cut probably about 50 turns off of the time I needed to win the game.
I had no idea that Shadows were so amazingly good until I noticed that Invisible doesn't go away when you attack. You only lose the Hidden promotion when you attack.
Also, for all of the people who complain about Nox Noctis, go build a couple of Hidden Nationality Assassins or even Rangers while you are waiting to tech your way to Shadows and you can attack your neighbors with impunity as long as you have an avenue to retreat back to home territory. Even if you don't have a path back home, you can hide your nationality on one turn and then attack on the next turn and declare nationality while you're still in the neighbor's territory. It takes a little longer, but it's still quite effective.
One final thought: Grigori heroes are born to become Archmagi, not puny little axemen and such.