The real achievement in my mind is not getting this. It's gonna be in the game until Deathwing is downed, so a very long time.
http://www.wowhead.com/achievement=5518/stood-in-the-fire would be more useful than Jaedenar forums for this, it has actual information.
A few useful excerpts/extrapolations from comments:
Southern Barrens - Battlescar N-S
Stonetalon Mountains - 70,80; 39,32.5
Tanaris - 38.5,62.6; 43.3,45.8; Gadgetzan NNE-SSW
Winterspring - 57,29
Arathi Highlands - 44,66 E-W << Most popular spot
Blasted Lands - 35,65; 66,42 N-S
Burning Steppes - 46,41; 65,45
Eastern Plaguelands - 62.5,42; 47,58.5; 50,59
Western Plaguelands - 50.5,53 N-S?
Wetlands - 25,36 NE-SW
There is speculation that he doesn't just randomly attack zones, but moves through different zones in a linear fashion (e.g. North to South or East to West). This isn't proven but seems likely.
Some people are reporting times of approximately 6 hours between each death, but it's unclear whether this is based on server, continent or zone (I myself haven't payed enough attention to notice).