Chemotaxis receptors in E. coli form clusters at the cell poles and also laterally along the cell body, and this clustering plays an important role in signal transduction. Recently, experiments using fluorescence imaging have shown that, during cell growth, lateral clusters form at positions approximately periodically spaced along the cell body. In this Letter, we demonstrate within a lattice model that such spatial organization could arise spontaneously from a stochastic nucleation mechanism. The same mechanism may explain the recent observation of periodic aggregates of misfolded proteins in E. coli.