Self-organized structure formation in the melt of hairy-rod polymers is analyzed theoretically. It is shown that the interplay between unfavorable repulsive rod-coil interactions and stretching of the side chains is responsible for the appearance of three different microphases: one lamellar and two hexagonal. The first-order phase transitions between these are considered in detail. If the side chains are long enough for the elastic stretching free energy to dominate the repulsive interactions, hexagonally ordered domains of hairy-rod cylindrical brushes are formed. The lamellar phase is shown to be stable for shorter side chains and occupies an important part of the phase diagram. In the intermediate side chain length regime another hexagonally ordered structure appears, characterized by cylindrical micelles with an elongated cross section, containing several hairy-rod polymers.