Combinatorial or random methods for strain engineering have been extensively used for improvement of multigenic phenotypes and other traits for which the underlying mechanism is not fully understood. The preferred method has been mutagenesis and selection, but other methods have emerged. Our lab has successfully used mutant transcription factors, which direct the RNA polymerase (RNAP) during transcription, to engineer complex phenotypes in yeast and bacteria. These phenotypes encompass tolerance to harsh process conditions and overproduction of metabolites of interest in Escherichia coli, Lactobacillus plantarum, and Saccharomyces cerevisiae. Here, we show that it is also possible to impart new phenotypes by mutating the RNAP holoenzyme itself, in particular, the alpha subunit of the bacterial polymerase. Using a previously-developed statistical metric, we show that a library of mutants constructed by error-prone PCR can introduce phenotypic diversity, and we use this fact for guiding our experimental efforts. Finally, we present the use of this tool for improving tolerance of E. coli to butanol and other solvents, and for increasing the titers of two commercially-relevant products, tyrosine and hyaluronic acid.