I believe they also appear on Route 2. Which is before the first Gym.
Nope, shaking grass does not activate until after getting the first Badge.
Clay's Excadrill can be kinda tough but it's not too difficult if you started with Oshawott or if you have any decent Water-type on your team. Fighting-types also do great against it.