We present a nanoscale low-power all-optical switching approach based on surface-plasmon polaritons (SPPs) by employing the concept behind Mach-Zehnder interferometer (MZI). The capabilities of SPPs to confine energy of electromagnetic waves in the subwavelength scale provide the possibility to design miniaturized all-optical switches. We employ nanoscale plasmonic waveguides in MZI and add a pump to the structure to provide on/off states in the all-optical switch. The waveguide cladding is made of lossy media including metamaterials, with positive and negative electromagnetic susceptibilities, and metals and the core consists of dielectrics and nonlinear media. By turning the pump on or off, the pump energy affects the Kerr nonlinear material in the waveguide core at one of the interferometer branches that provides constructive or destructive interferences between propagating SPPs in the up and down branches of the interferometer. Employing metamaterials, instead of commonly used metals, in the switch structure facilitates the propagation of both transverse electric and transverse magnetic SPPs along the waveguides, which enables on/off states for both transverse electric and transverse magnetic modes in the switch. Our all-optical switch design enables multi-frequency switching with low-intensity pump field. Ascertaining the capabilities of multi-frequency plasmonic all-optical switches facilities their applications in miniaturized photonic circuits.