It would be somewhat difficult, but nowhere near impossible. People have been doing those sorts of challenges since Red and Blue/Green came out. The Eviolite in Black and White makes it even easier (it boosts unevolved Pokémon's defenses by 50%). Plenty of unevolved Pokémon are perfectly capable of doing that sort of challenge. Some can even outclass certain fully evolved Pokémon. A few examples are: Light Ball Pikachu, Scyther, DeepSeaTooth Clampearl, Munchlax, etc. Let's not forget single stage Pokémon such as Tauros or Smeargle.
Overall, a challenge such as this would require much more strategy than brute strength (as well as a bit of level grinding), but it is entirely possible.