My short, short suggestion is… don’t: This blog post explains it much better than I can although I definitely have been the victim of trying to generate a GPG key on a headless server to no avail:
While trying to generate a gpg keypair on a remote server, I discovered I lack entropy. Eventually I had to physically type on the keyboard in order to generate enough random bytes.
I guess in the meantime the best workaround is to generate a GPG key on a workstation somewhere and transfer that to the server in question. A little hokey but I guess if you truly need a GPG key that would be my suggestion.