Sandshrew can be found in the following areas: Routes 4, 8, 9, 10, 11, and 23. Sandslash can be found in the following areas: Route 23 and Victory Road. It is a LeafGreen exclusive, and cannot be found in FireRed.
This pangolin/wolverine thing wrecks like Generation V Excadrill. Whereas its counterpart, Arbok, can nerf Attack and administer status effects, Sandslash can, under the right circumstances, drain the HP and PP of its enemies. Even without the viability of its ability, Sand Veil, this thing can dish out as much punishment as it can take, which is saying something. If you prefer LeafGreen over FireRed, you might want to use one (because you'll probably pick one up sooner or later).
Rival (Cerulean City): If at least some training was done, the rival here is weaksauce, especially if you chose this version's mascot. Pidgeotto may be a little challenging, but Potion stall always works. Same for Rattata, if it manages to crit (always expect). Abra is obvious at this point. All of the starters are dangerous since they have relatively strong special-based attacks, and Sandshrew's Special Defense is pretty bad.
Gym #2 - Misty (Cerulean City, Water-type): Hahahahaha... seriously, no. STAB Water Pulse on something that's weak to it? Don't.
Rival (S.S. Anne): Everything remains the same, except that you might need a few Potions against Kadabra. However, since you'll probably be evolved and packing Dig by this point, you should be fine.
Gym #3 - Lt. Surge (Vermillion City, Electric-type): If you decided to hold off on Diglett's Cave, Sandslash easily takes its place with more bulk to cover its comparative lack of Speed. Sandshrew/Sandslash lack the fantastic spam move that Diglett has in Magnitude, but it can still OHKO everything in this gym with Dig (hopefully).
Rival (Pokémon Tower): Avoid Gyarados, but don't be afraid to go against Growlithe even though it will drop your Attack with Intimidate. Dig can still make short work of it easily. Of course, avoid the Grass-type.
Giovanni (Rocket Hideout, Ground-type): This could easily be a Sandslash sweep, especially if it knows both Dig and Brick Break. Apply Potion to areas affected by Mega Punch.
Gym #4 - Erika (Celadon City, Grass-type): Another pass. Don't ask why, just don't.
Gym #5 - Koga (Fuchsia City, Poison-type): With the proper amount of healing items, this gym is acceptable in terms of Sandlash's viability. However, remember that your STAB Ground-type moves won't be able to hit Koffing or Weezing. Muk could be a knock-down, dragged-out fight, but on the off chance you taught Sandslash Swift or Aerial Ace, that's one fewer strategy that Koga can employ.
Fighting Dojo (Saffron City, Fighting-type): This is a neutral ground unless taught the previously mentioned Aerial Ace. Then its a bloodbath, even against Ice Punch Hitmonchan (because lol 35 base Special Attack).
Rival (Silph Co.): Same as before. Kadabra is an Alakazam now, so it will be more dangerous, but it "only" has Future Sight to hit with, which is fairly predictable. Sandslash may kill it with a strong Normal move before it gets to use it. Again, avoid any Grass- or Water-types.
Giovanni (Silph Co., Ground-type): More options for Sandslash than previously. Watch for Poison Point on Nidoqueen, but the poison status is not as frightening at this point in the game and otherwise, Giovanni can't really touch you.
Gym #6 - Sabrina (Saffron City, Psychic-type): Sandslash's mediocre Special Defense makes this a very bad idea.
Gym #7 - Blaine (Cinnabar Island, Fire-type): Have fun with how many ways you can work over the psychotic pyro. Dig is more than sufficient, but you may need a switch-out or two, to get rid of the pesky Intimidate by Growlithe and Arcanine.
Gym #8 - Giovanni (Viridian City, Ground-type): More of the same thing, except that Dugtrio is a 50/50 shot. Remember not to use Dig in this battle, since everything has Earthquake, which will double in power if it hits you while you're underground.
Rival (Route 22, pre-Elite Four): Feel free to make use of Earthquake against Rhyhorn if you taught it. The rest works the same way as before: no Grass or Water, while Fire is easy work. Pidgeot too. Avoid Alakazam as it now has Psychic.
Elite Four Lorelei (Indigo Plateau, Ice-type): Can I has a HELL NO? Everything here kills Sandslash easily.
Elite Four Bruno (Indigo Plateau, Fighting-type): YASS (Yet Another Sandslash Sweep). Sandslash can take down the two Onix and the Hitmons easily thanks to it being able to use Earthquake off of its high Attack stat. Machamp is bulky, but Sandslash is more so; unless you get critted by Cross Chop, you should win the power war there.
Elite Four Agatha (Indigo Plateau, Poison-type): Arbok and Golbat because you can. Does not agree with Ghosts, since they have Levitate, but their essentially physical movesets make them non-threatening if you have coverage that can hit them, like Rock Slide.
Elite Four Lance (Indigo Plateau, Dragon-type): Too much risk, not enough reward. Although, you can use it as an Aerodactyl counter if it has Rock Slide.
Champion Rival (Indigo Plateau): Nothing too different, except that Exeggutor can hurt, so avoid that. Sandslash averagely fares well for about half of this team, and needs to avoid the other half, regardless of the rival's starter.
Post-Game: Will be added sometime later on. Just know that fighting Mewtwo is a bad idea.
Pretty soon after you get Sandshrew, the awesome Dig will become available. It has a decent base 60 power (90 with STAB), and will be your primary move for almost the entire game. Aside from that, though, Sandshrew and Sandslash have pretty barren movepools. Sandshrew will get Scratch and Poison Sting pretty early for attacking options, but both of those suck. Sand Attack can be decent for hax, but you should never rely on hax in a Nuzlocke. Slash comes very soon after Sandshrew evolves (level 24), and that will be a very welcome addition to its moveset. Swift can be useful, if only against pieces of crap that like to spam Sand Attack, Minimize, or Double Team. Sandstorm can be worth looking at, but it comes at Level 62, which you probably won't reach unless you overgrinded massively.
Sandslash doesn't get much from TMs or Move Tutors, but it gets what it needs. As mentioned before, Dig is available as soon as you save that wimpy Cerulean family from the Rocket Grunt in their backyard, and that will be all you need for a while. The TM for Aerial Ace can be found on the route leading up to Rock Tunnel, and that will be a very welcome addition to Sandslash's moveset, allowing it to hit the Grass-types and Bug-types that resist its STAB. Brick Break, which is a purchasable TM from the Celadon Department Store (it can also be found on the S.S. Anne), is also very good for Sandslash, since it can hit Normal-types and Ice-types. Rock Slide, which is taught by a Move Tutor in Rock Tunnel, is one of the best moves Sandslash can get, as it gives it a tremendous pseudo-EdgeQuake combo. Finally, after beating Giovanni in the Viridian Gym battle, he'll give you TM26 Earthquake, which is a godsend for Sandslash. Slap Earthquake on that bad boy and start wrecking things. Easy as pie.
Recommended moveset: Earthquake, Aerial Ace, Rock Slide, Brick Break
Minimum stats are calculated with 0 EVs, IVs of 0, and a hindering nature, if applicable.
Maximum stats are calculated with 252 EVs, IVs of 31, and a helpful nature, if applicable.
Sandshrew Line Ratings
What Nature do I want? Adamant is the best by far. Brave is okay, as is any other Attack-boosting Nature. Speed-boosting Natures are fine as well, as long as you don't get Timid. A Nature that boosts Special Attack is not optimal, especially Modest (blech).
At what point in the game should I be evolved? Before Misty, ideally. You should definitely have evolved into a Sandslash by the time you reach the SS Anne.
How good is the Sandshrew line in a Nuzlocke? It's quite good. It has the physical bulk and the typing to tank pretty much any physical hit thrown at it, and it can retaliate with very strong attacks of its own. It's one of the better tanks in the game that isn't Water-type. Plus, it's rather common. It matches up very well against the numerous Poison-types that plague Kanto, and it has more than enough Defense to survive a non-crit SelfDestruct or Explosion. Sandslash is definitely a great team player.