<<Disclaimer: Verify this information before applying it to your situation.>>

Jelly Belly makes a gf black jelly bean.  Also Pearson's Licorice Nips
were gf last time I checked.  They're a black licorice lozenge you suck
on.  I think the Pearson's Licorice Nips are a Hershey product.  We're
still out of luck on the red licorice as far as I know.