In response to a concentration gradient of nutrient, E. coli bacterium modulates the rotational bias of flagellar motors which control its run-and-tumble motion, to migrate towards regions of high nutrient concentration. Presence of stochastic noise in the biochemical pathway of the cell has important consequence on the switching mechanism of motor bias, which in turn affects the runs and tumbles of the cell. We model the intra-cellular reaction network in terms of coupled time-evolution of three stochastic variables, kinase activity, methylation level and CheY-P protein level, and study the effect of methylation noise on the chemotactic performance of the cell. In presence of a spatially varying nutrient concentration profile, a good chemotactic performance allows the cell to climb up the concentration gradient fast and localize in the nutrient-rich regions in the long time limit. Our simulations show that the best performance is obtained at an optimal noise strength. While it is expected that chemotaxis will be weaker for very large noise, it is counter-intuitive that the performance worsens even when noise level falls below a certain value. We explain this striking result by detailed analysis of CheY-P protein level statistics for different noise strengths. We show that when the CheY-P level falls below a certain (noise-dependent) threshold, the cell tends to move down the concentration gradient of the nutrient, which has a detrimental effect on its chemotactic response. This threshold value decreases as noise is increased, and this effect is responsible for noise-induced enhancement of chemotactic performance. In a harsh chemical environment, when the nutrient degrades with time, the amount of nutrient intercepted by the cell trajectory, is an effective performance criterion. In this case also, we find an optimum noise strength, depending on the nutrient lifetime.