Sensitive Herschel far-infrared observations can break degeneracies that were inherent to previous studies of star formation in high-z AGN hosts. Combining PACS 100 and 160 mum observations of the GOODS-N field with 2 Ms Chandra data, we detect 20% of X-ray AGN individually at >3sigma. The host far-infrared luminosity of AGN with L2-10 keV &ap; 1043 erg s-1 increases with redshift by an order of magnitude from z = 0 to z 1. In contrast, there is little dependence of far-infrared luminosity on AGN luminosity, for {L2-10 keV} &lap; 1044 erg s-1 AGN at z &gap; 1. We do not find a dependence of far-infrared luminosity on X-ray obscuring column, for our sample which is dominated by L2-10 keV < 1044 erg s-1 AGN. In conjunction with properties of local and luminous high-z AGN, we interpret these results as reflecting the interplay between two paths of AGN/host coevolution. A correlation of AGN luminosity and host star formation is traced locally over a wide range of luminosities and also extends to luminous high-z AGN. This correlation reflects an evolutionary connection, likely via merging. For lower AGN luminosities, star formation is similar to that in non-active massive galaxies and shows little dependence on AGN luminosity. The level of this secular, non-merger driven star formation increasingly dominates over the correlation at increasing redshift. Herschel is an ESA space observatory with science instruments provided by European-led Principal Investigator consortia and with important participation from NASA.