We develop the weak segregation theory of micro phase separation in stoichiometric blends of oppositely and weakly charged polyelectrolytes, which would be immiscible in the absence of charged units. Short-range repulsions between polycation and polyanion monomers induce the formation of oppositely charged domains, the size of which is controlled by their excess Coulomb energy. The diagram of blend morphologies is constructed in the framework of Leibler's mean-field approach and to account for fluctuations within the Brazovskii-Fredrickson-Helfand approximation. Phase behavior of the polyelectrolyte blends is fully analogous to that of neutral diblock copolymers. The mean-field analysis predicts that the order-disorder transition (ODT) is second order for the symmetric blend. In asymmetric mixtures, an increasing incompatibility between polyelectrolytes triggers the usual cascade of first-order phase transitions, dis -> bcc -> hex -> lam. Fluctuations alter the phase diagram topology and allow the direct transitions from the disordered state (dis) to hex and lam microphases; for the symmetric blend, ODT becomes weakly first order. We also discuss that both microphase separation in polyelectrolyte blends and the formation of nuclear "pasta" phases within neutron stars are governed by similar physical principles, despite the 6 orders of magnitude difference in the periods of these structures.