After beating the first gym head to the north west exit from the city and there will be a person who gives you rock smash. After beating blue(gary) in kanto Prof. Oak will give rock climb to you when you go to his lab in pallet town.
Go left of Violet city and go through the green house then there will be a fat man, talk to him and he will give you Rock smash, to get Rock Climb you must get all 16 badges and talk to proffeser oak.
