Everyone has their own method for using Stash and the various caching tools.
I find that Stash is great for simplifying my structure (more DRY) which also has a side effect of dropping overhead. But my first goal with Stash is "stashing" a block of functionality so that I can move it elsewhere within my "waterfall" of template rendering and / or cloning that block to be used in multiple areas.
Caching with add-ons such as CE Cash and Template Morsels (from Solspace and similiar functionality as CE Cache) is great for making a dynamic area load as a static area (with control over refresh intervals) but not so great at moving that component elsewhere in the waterfall and not as great as Stash is for fine grained re-usability of code.
Stash has been pretty quick moving in added functionality and details can change quick, but in the past I have found caching tools like Template Morsels easier for just setting entire sections of templates as being cached and going on about my day. With Stash I'm much more targeted.
So, yes, Stash and caching options should be used side by side. Each option gives you similar answers to performance problem but I use them differently based on their differing capabilities.