One of the random storms creates uberdoomskulls, see [REPORTED] New Storm Needs Appropriate Label.
However, I don’t know whether that storm is turned off when uberdoomskulls are turned off. I just played a few matches with the Chaos Storm talent, but didn’t see an uberdoomstorm (had 3 bonestorms and 2 doomstorms). Even if you can get the storm, you’ll see it so infrequently grinding the achievement will be a real chore.
To get a random storm, either use the Stormsinger troop or the Chaos Storm talent in Archmagus, Barbarian, Deathknight, Dervish, Frostmage, Stormcaller or Titan.