Run-and-tumble motility is widely used by swimming microorganisms including numerous prokaryotic and eukaryotic organisms. Here, we experimentally investigate the run-and-tumble dynamics of the bacterium E. coli in polymeric solutions. We find that even small amounts of polymer in solution can drastically change E. coli dynamics: cells tumble less and their velocity increases, leading to an enhancement in cell translational diffusion and a sharp decline in rotational diffusion. We show that suppression of tumbling is due to fluid viscosity while the enhancement in swimming speed is mainly due to fluid elasticity. Visualization of single fluorescently labeled DNA polymers reveals that the flow generated by individual E. coli is sufficiently strong to stretch polymer molecules and induce elastic stresses in the fluid, which in turn can act on the cell in such a way to enhance its transport. Our results show that the transport and spread of chemotactic cells can be independently modified and controlled by the fluid material properties.