This is huge. No other move had every affected the game as much as Stealth Rock, not even Scald.
As stated, the most obvious change would be the overhaul of the lead metagame. With no race for hazards (Spikes just doesn't cut it, you need a dedicated setter that can reliably do it during the heat of the match, plus Frosslass isn't good), you're down to just attacking leads and Choice mons.
Flyers get a huge buff. Zapdos does well already even with rocks, but now it can last forever with Roost. Same for Gyarados, and the RestTalk set becomes almost flawless. My favorite thought, Yanmega would come back (nostalgia). Salamence would have had little issues back in the day and would have gotten banned sooner in Platinum. Moltres would certainly make it big with its Choice sets and especially SubRoost (would also be one of the many reasons Shaymin would never exist).
The game would have been so different in terms of how playstyles in 4th gen functioned. Whether running offense, stall, or balance, you maximize your team's potential with rocks. Balance would probably take a hit however. You use hazards (especially rocks) to beat stall. Without it, you can't consistently break through some of the best cores. Stall uses hazards to put actual pressure on other teams to beat them in time. They lose a lot of that ability, but will still do well in general. Offense also takes a hit without the extra damage on switch-ins. Hyper, a little less because it's based on constant pressure, and a lot of DPP mons are used to the whole "one shot/chance to work" thing.