A new class of ultra-long duration (>10,000 s) gamma-ray bursts has recently been suggested. They may originate in the explosion of stars with much larger radii than normal long gamma-ray bursts or in the tidal disruptions of a star. No clear supernova had yet been associated with an ultra-long gamma-ray burst. Here we report that a supernova (2011kl) was associated with the ultra-long duration burst 111209A, at z=0.677. This supernova is more than 3 times more luminous than type Ic supernovae associated with long gamma-ray bursts, and its spectrum is distinctly different. The continuum slope resembles those of super-luminous supernovae, but extends farther down into the rest-frame ultra-violet implying a low metal content. The light curve evolves much more rapidly than super-luminous supernovae. The combination of high luminosity and low metal-line opacity cannot be reconciled with typical type Ic supernovae, but can be reproduced by a model where extra energy is injected by a strongly magnetized neutron star (a magnetar), which has also been proposed as the explanation for super-luminous supernovae.