Let's face it: your first bought with a Totem Pokemon should be breeze no matter the Pokemon you have when facing it. Gumshoos won't pose too many threats since it's not that great of a Pokemon to begin with, as well as because it will only have its Defense Stat raised when the battle commences.
However, if you are having some difficulties with it, there are a few things you can do to better be prepared. The first, of course, is to raise your Pokemon. Even just a few extra levels before facing your Verdant Cavern Trial could make a whole lot of difference when facing Totem Gumshoos. Another thing you can do is trade with the person in the Route 2 Pokemon Center for Hawlucha. Hawlucha is a great Pokemon, and it strikes Gumshoos HARD. Lastly, making sure your Pokemon going to the battle fully healed will always prove to be key.
When facing Totem Gumshoos later in the Post Game, you will see virtually the same exact Pokemon, outside of it now reaching Level 60 and having all of its Stats raised. However, by then, your Pokemon should have way better leveling then it, making it just a easy to defeat as before. Simply do as the first time when facing it, bringing in a strong Fighting Type and five other healthy Pokemon. You'll be fine.