In Canalve City, sail to Iron Island. Go down all the way to where there are 2 staircases to take (one going west and the other east). The eastern one leads to Riley, a blue-clothed guy who follows and helps you battle other Trainers. The western staircase leads to a Pokéball containing Iron Tail. That place is small, so you'll find it easily.
So if you have already been through Iron Island it should be a breeze to get.