Building net-libs/gnutls with the tools USE flag (which build gnutls-cli) resolved this issue for me, so perhaps app-emacs/flycheck should have a dependency for that?
Sorry I was to quick (and confused), so I change this to INVALID.