That shouldn't be a problem, really. I wasn't familiar with any of the new Pokemon either, and I did just fine.
And silly Deoxys121, you can't get any ice-types at that stage in the game. They don't pop up until Twist Mountain, iirc. So yeah, keep on with your Sandile, and learn to predict Volt Switches to give yourself the advantage. In addition, Sandile effectively blocks VS, which can give you a huge advantage. What level is the little fella?