Route 657

Items:
Revive x1 
Ultra Ball x1 
Super Potion x1 
Calcium x1 
TM19 
TM67 (Requires Cut) 
PPUP (Requires Surf - Hiding south) 

Trainers: 
Cyclist Krissa - Aipom Lv. 18, Ledian Lv. 18 
Cyclist Hector - Combee Lv. 18, Cherubi Lv. 18 
Lady Sophie - Flaaffy Lv. 20 
Richboy Brad - Watchog Lv. 20 
Pokémon Ranger Anja - Pineco Lv. 18, Clefable Lv. 18, Roselia Lv. 18, Bibarel Lv. 18 
Pokémon Ranger Steve* - Venipede Lv. 18, Drifloon Lv. 20 
*Get number 

Alright, we've come full circle. Since this area is primary meant for headbutting, I'll leave the list here. 

Headbutt Pokémon: 
Lv. 10-15 
(Low) 
Ledyba - 30% 
Aipom - 25% 
Pineco - 20% 
Cherubi - 20% 
(High) 
Combee - 30% 
Spinarak - 25% 
Burmy - 20% 
Seedot - 20% 

Also, now that you have surf, here's the Pokémon you'll encounter in the water. 

Moving Water 
Lv. 20-30 
Wingull - 50% 
Wailmer - 30% 
Frillish - 10% 
Shellos - 10% 

Calm water 
Lv. 20-30 
Tentacool - 50% 
Marill - 30% 
Slowpoke - 10% 
Corphish - 10% 

I say take this time to have a rematch those trainers close by. You're not going to get Fly for a little while longer. 

If you want, you can head back to Pebble Cave and surf to the new section.

Pebble Cave (Part 2)Pokémon:Lv. 23-25
Bronzor - 25%
Bagon - 25%
Drilbur - 15%
Aron - 15%
Diglett - 10%
Larvitar - 10%

Items:Escape Rope x1
Hard Stone
Focus Sash
TM78

Trainers:Worker Paul - Bronzor Lv. 25, Drilbur Lv. 25
Worker Scott - Diglett Lv. 25, Bagon Lv. 25
Worker Zack - Aron Lv. 25, Larvitar Lv. 25

You can play the mine minigame once a day by talking to the hiker. Use Rock Smash on the rocks to undercover fossils.

Cyclopes 

Items: 
Repeat Ball x1 
Water/Fire/Leaf Stone (Talk to girl in westmost house) 
Expert Belt (Hiding behind the trees next to the westmost house) 
Heart Scale (Hidden in flowers) 
Shell Bell (Talk to woman in the northeast house) 
TAKON TICKET (Talk to the guy in the southeast house upstairs) 

The fisherman that lives with the Shell Bell woman will give you a new Heart Scale everyday. I put TAKON TICKET in caps because you don't want to overlook this. The guy upstairs is the one to deliver Milla's letter to. He'll ask you to give Milla one last letter. Go back to her place to do so, THEN COME BACK AND TALK TO THIS GUY AGAIN ASAP. He'll thank you for delivering the letter and give you the ticket. I put so much emphasis on this because he'll leave after you get your eighth badge, meaning you don't get the ticket if you haven't by that point. Which means you can say bye-bye to getting Mew and Mewtwo. You can wait until you have Fly to finish this, but I wouldn't put it off for any longer than that. 

Anyway, since there's Magnemite blocking the east path, you're going to have to head south to investigate. Yes, this means you need surf to continue with the story. 

Ironwork Factory (Exterior) 

Pokémon: 
Lv. 17-19 
Voltorb - 25% 
Foongus - 25% 
Machop - 15% 
Buizel - 15% 
Pachirisu - 10% 
Natu - 10% 

Items: 
Protein x1 
Dive Ball x1 
Rocky Helmet (Talk to guy behind building) 

Trainers: 
Swimmer Wright - Wailmer Lv. 20 
Swimmer Ruth - Tentacool Lv. 20, Wingull Lv. 20 
Policeman Dell - Growlithe Lv. 18, Machop Lv. 18 
Worker Leo - Geodude Lv. 18, Magby Lv. 18, Koffing Lv. 18 

This is the place where you'll get to catch those Pokémon you saw other trainers have. Once you're happy with everything outside, it's time to go in. 

Ironwork Factory (Interior) 

Pokémon: 
Lv. 18-20 
Grimer - 25% 
Magnemite - 25% 
Elekid - 15% 
Magby - 15% 
Koffing - 10% 
Trubbish - 10% 

Items: 
Super Potion x1 
Ether x1 
Nest Ball x1 
Ice Heal x1 
Magnet 
TM72 

Trainers: 
Worker Niel - Roggenrola Lv. 20, Grimer Lv. 20 
Worker Gus - Trubbish Lv. 20, Elekid Lv. 20 
Scientist Ronald - Magnemite Lv. 20 
Scientist Terrance - Magby Lv. 20, Pachirisu Lv. 20 
Scientist Franklin - Voltorb Lv. 19, Foongus Lv. 19, Natu Lv. 20 
Scientist Lumina - Koffing Lv. 20 
Scientist Marie - Elekid Lv. 20, Buizel Lv. 20 
Scientist Caroline - Electrike Lv. 20, Shelmet Lv. 20, Grimer Lv. 20 
Female Grunt - Liepard Lv. 24, Nuzleaf Lv. 24 

Examine the test tubes if you're curious to see what's inside. You can evolve Magneton here if you want. Taking the stairs to the northwest will take you to a basement with a Scientist. He'll give you a Rotom, and the boxes surrounding him contain things that Rotom can possess. To the northeast is the stairs to an office, where Team Annhiliation is up to no good. Help Hercules beat them up and you'll get a Nugget when you talk to the president afterward. There's also Leftovers in his trashbin. Score! 

Route 658 

Pokémon: 
Lv. 19-21 
Snubbull - 25% 
Paras - 25% 
Timburr - 15% 
Stunky - 15% 
Munna - 10% 
Emolga - 10% 

Items: 
Leppa Berries x2 
Hyper Potion x1 
Shiny Stone x1 
PPUP x1 
TM76 
TM83 (Requires Strength) 

Trainers: 
Parasol Girl April - Goldeen Lv. 22, Frillish Lv. 22 
Painter Horton - Munna Lv. 22 
Cyclist Axel* - Emolga Lv. 22, Paras Lv. 22 
Cyclist Kayla* - Emolga Lv. 21, Snubbull Lv. 22, Tranquill Lv. 22 
Gentleman Robert - Growlithe Lv. 22, Timburr Lv. 22 
Madame Grace - Liepard Lv. 22, Roselia Lv. 22 
*Get number 

Nothing special here. Just grab, fight, and move on. 

Palioxis 

Items: 
Rare Candy x1 
Max Repel x1 
Elixir x1 
Sharp Beak (Talk to the woman in the northwest house) 
TM62 (Talk to the girl in the southwest house) 

Pokémon: 
Slowking (Trade a Poliwrath) 
Politoed (Trade a Slowbro) 

Jump over the logs! You'll find out the gym leader isn't here. Since the east gate is blocked off, there's only one other way to go. 

Graveyard Tower (Exterior) 

Items: 
Dusk Stone x1 

Some of the tombs are readable. 

Graveyard Tower (Interior) 

Pokémon: 
Lv. 20-22 
Shuppet - 25% 
Duskull - 25% 
Yamask - 15% 
Litwick - 15% 
Gastly - 10% 
Spiritomb - 10% 

Items: 
Revive x1 
Dusk Ball x1 
Hyper Potion x1 
Spell Tag 
TM61 
TM65 

Trainers: 
Psychic Doreen - Drowzee Lv 24, Shuppet Lv. 24 
Psychic Perry - Kirila Lv. 24, Gastly Lv. 24 
Psychic Bruce - Kadabra Lv. 24, Duskull Lv. 24 
Pokéfan Georgia - Clefable Lv. 24 
Psychic Dua - Munna Lv. 24, Spiritomb Lv. 24 
Pokéfan Elliot - Pachirisu Lv. 24, Litwick Lv. 24, Yamask Lv. 24 

You can't pass the spirits. Maze through the tower until you reach the end. There you'll have to stop the tower from being blown up. 

Aedus 
Koffing - Lv. 30 
Electrode - Lv 30 
Forretress - Lv. 32 
Nuzleaf - Lv. 32 

They still try to blow you up with Explosion/Self-Destruct. Better you than the tower, right? You get HM02 for it though. Man, what's it about gym leaders giving out HMs you can't even use yet? 

Fifth Gym 

Trainers: 
Pokémon Breeder Marcus - Tranquill Lv. 25, Skiploom Lv. 25 
Nursery Aide Autumn - Swellow Lv. 25, Pidgeotto Lv. 25, Pelipper Lv. 25 
Pokémon Ranger Briana - Noctowl Lv. 25 

You have to beat the trainer that will remove to rock blocking the gym leader. 

Gym Leader - Callum
Togekiss - Serene Grace - Sitrus Berry - Lvl 30 
•Air Slash 
•Aura Sphere 
•Roost 
•Aerial Ace 
Xatu - Magic Bounce - Sitrus Berry - Lvl 32 
•Night Shade 
•Confuse Ray 
•Psyshock 
•Aerial Ace 
Staraptor - Reckless - Sitrus Berry - Lvl 34 
•Double Team 
•Take Down 
•Roost 
•Aerial Ace 
Obtain TM40 - Aerial Ace 

Feels like forever since the last one, huh? Don't underestimate his Pokémon. There might only be three, but they pack a punch.

Oasis Desert

Pokémon:
Lv. 21-23
Sandshrew - 25%
Sandile - 25%
Maractus - 15%
Cacnea - 15%
Phanpy - 10%
Gible - 10%

Items:
Brightpowder x1
Lemonade x1
Burn Heal x1
Sun Stone x1
Ultra Ball x1
TM39
Pokémon Egg (Talk to woman in route gate)
Oval Stone (Talk to woman after egg hatches)

Trainers:
Backpacker Ivan* - Sandile Lv. 26, Sandslash Lv. 26, Cacnea Lv. 26
Backpacker Blossom* - Maractus Lv. 26, Gabite Lv. 26, Donphan Lv. 26
Backpacker Sam - Golbat Lv. 26, Sandslash Lv. 26
Backpacker Annie - Watchog Lv. 26, Sandile Lv. 26
Hiker Jeremy - Shuckle Lv. 26 x4
Hiker Doug - Onix Lv. 26 x3, Graveler Lv. 26

Rock Smash Pokémon:
Dwebble - 50%
Onix - 30%
Slumga - 10%
Shuckle - 10%

Time to kick things up. Now trainers will have 2-4 Pokémon on average, which will be at least 2 levels higher than the wild ones. This means they might already have an evolved form of it! You'll notice a waterfall to the northwest. This takes you to the second half of the desert when you have the HM for it. In case you decided to come in from the other entrance, here's the information for it now.

Oasis Desert (Part 2)

Pokémon:
Lv. 21-23
Hippopotas - 25%
Torkoal - 25%
Carnivine - 15%
Baltoy - 15%
Trapinch - 10%
Darumaka - 10%

Items:
Enigma Berries x2
Hyperpotion x1
Soft Sand
Iron x1 (Requires Waterfall)
Stardust (Requires Waterfall)
TM26 (Requires Waterfall)

Trainers:
Backpacker Kendall - Hippopotas Lv. 26, Torkoal Lv. 26, Trapinch Lv. 26
Backpacker Jill - Baltoy Lv. 26, Carnivine Lv. 26, Darumaka Lv. 26
Fisherman Sid - Basculin Lv. 26, Luvdisc Lv. 26, Stunfisk Lv. 26, Staryu Lv. 26

Those berries are needed for a side quest, so grab them while you're at it.

Route 659

Pokémon:
Lv. 22-24
Deerling - 25%
Gulpin - 25%
Gothita - 15%
Solosis - 15%
Swablu - 10%
Joltik - 10%

Items:
Elixir x1
Calcium x1
Balm Mushroom (Hidden in flowers)
TM06 (Requires Strength)

Trainers:
Doctor Kit - Audino Lv. 25, Joltik Lv. 25
Cool Trainer Charlie - Lombre Lv. 26, Flaaffy Lv. 26, Vigoroth Lv. 26
Cool Trainer Jamie - Palpitoad Lv. 26, Arbok Lv. 26, Manectric Lv. 26
Psychic Nandor* - Solosis Lv. 26, Drifloon Lv. 26, Hypno Lv. 26
Psychic Ena* - Gothita Lv. 26, Haunter Lv. 26, Metang Lv. 26
Nursery Aide Kimya - Swablu Lv. 26, Deerling Lv. 26, Swalot Lv. 26, Simisear Lv. 26
Preschooler Buster - Simipour Lv. 26, Ariados Lv. 26
Preschooler Lin - Simisage Lv. 26, Mothim Lv. 26

Once again heal with the good doctor and fight your way to the next town.

Dikaiosyne

Items:
Full Heal x1
Repeat Ball x1
Black Belt
Amulet Coin (Talk to girl in house near Pokécenter)
Soothe Bell (Talk to woman in dept. store)

Pokémon:
Porygon (Purchase from shady guy)
Porygon2 (Purchase from shady guy)
PorygonZ (Trade Porygon2s with youngster upstairs)

This is where you buy everything you need! And I mean everything. Incense, evolution stones, you name it. Speaking of, if you haven't done so yet, go evolve your Pokémon that needs a held item. Pokémon you would normally trade with these now evolve by leveling up with it instead. Gen 2 mon evolve during the day, while Gen 4 mon evolve at night. Now that you're all stocked and powered up, head to the gym!

Sixth Gym

Trainers:
Smasher Mari - Riolu Lv. 28, Sawk Lv. 28, Hariyama Lv. 28
Linebacker Bob - Riolu Lv. 28, Throh Lv. 28, Primeape Lv. 28
Hoopster Nicolas - Riolu Lv. 28, Gurdurr Lv. 28
Striker Tony - Riolu Lv. 28, Poliwhirl Lv. 28, Machoke Lv. 28, Breloom Lv. 28
Infielder Connor - Riolu Lv. 28, Lucario Lv. 28

You have to beat the trainers to be considered worthy to proceed.

Gym Leader - Gabriela 
Hitmontop - Technician - Sitrus Berry- Lvl 34
•Toxic
•Foresight
•Triple Kick
•Low Sweep
Poliwrath - Water Absorb - Sitrus Berry - Lvl 35
•Hypnosis
•Wake-Up Slap
•Bubblebeam
•Low Sweep
Machamp - No Guard - Sitrus Berry - Lvl 36
•Karate Chop
•Thunder Punch
•Stone Edge
•Low Sweep
Lucario - Inner Focus - Sitrus Berry - Lvl 38
•Swords Dance
•Bullet Punch
•Ice Punch
•Low Sweep
Obtain TM47 - Low Sweep

Big hitters use big attacks. Approach with caution.