We report the discovery by the Swift hard X-ray monitor of the transient source Swift J2058.4+0516 (Sw J2058+05). Our multi-wavelength follow-up campaign uncovered a long-lived (duration >~ months), luminous X-ray (L_X,iso ~ 3 x 10^47 erg s^-1) and radio (nu L_nu,iso ~ 10^42 erg s^-1) counterpart. The associated optical emission, however, from which we measure a redshift of 1.1853, is relatively faint, and this is not due to a large amount of dust extinction in the host galaxy. Based on numerous similarities with the recently discovered GRB 110328A / Swift J164449.3+573451 (Sw J1644+57), we suggest that Sw J2058+05 may be the second member of a new class of relativistic outbursts resulting from the tidal disruption of a star by a supermassive black hole. If so, the relative rarity of these sources (compared with the expected rate of tidal disruptions) implies that either these outflows are extremely narrowly collimated (theta < 1 degree), or only a small fraction of tidal disruptions generate relativistic ejecta. Analogous to the case of long-duration gamma-ray bursts and core-collapse supernovae, we speculate that rapid spin of the black hole may be a necessary condition to generate the relativistic component. Alternatively, if powered by gas accretion (i.e., an active galactic nucleus [AGN]), Sw J2058+05 would seem to represent a new mode of variability in these sources, as the observed properties appear largely inconsistent with known classes of AGNs capable of generating relativistic jets (blazars, narrow-line Seyfert 1 galaxies).