Self-healing polymers crosslinked by solely reversible bonds are intrinsically weaker than common covalently crosslinked networks. Introducing covalent crosslinks into a reversible network would improve mechanical strength. It is challenging, however, to apply this design concept to dry elastomers, largely because reversible crosslinks such as hydrogen bonds are often polar motifs, whereas covalent crosslinks are non-polar motifs, and these two types of bonds are intrinsically immiscible without co-solvents. Here we design and fabricate a hybrid polymer network by crosslinking randomly branched polymers carrying motifs that can form both reversible hydrogen bonds and permanent covalent crosslinks. The randomly branched polymer links such two types of bonds and forces them to mix on the molecular level without co-solvents. This allows us to create a hybrid dry elastomer that is very tough with a fracture energy $13,500J/m^2$ comparable to that of natural rubber; moreover, the elastomer can self-heal at room temperature with a recovered tensile strength 4 MPa similar to that of existing self-healing elastomers. The concept of forcing covalent and reversible bonds to mix at molecular scale to create a homogenous network is quite general and should enable development of tough, self-healing polymers of practical usage.