We report on the first demonstration of broadband tunable, single-mode plasmonic nanolasers (spasers) emitting in the full visible spectrum. These nanolasers are based on a single metal-oxide-semiconductor nanostructure platform comprising of InGaN/GaN semiconductor nanorods supported on an Al2O3-capped epitaxial Ag film. In particular, all-color lasing in subdiffraction plasmonic resonators is achieved via a novel mechanism based on a property of weak size dependence inherent in spasers. Moreover, we have successfully reduced the continuous-wave (CW) lasing thresholds to ultrasmall values for all three primary colors and have clearly demonstrated the possibility of "thresholdless" lasing for the blue plasmonic nanolaser.