Yes, it was definitely a print story, though I don't remember if I read it in one of the many sci-fi magazines published back then, or whether it might have been in an anthology. Reading the different comments posted here made me realize that I left two things out that maybe can be "triggers" to memory -- one was the tone of the story. Unlike Sandkings, in which the main character had an attitude akin to arrogance, the tone of the story I am referring to was much more like that of "Ratman's Notebook," a man betraying the strong loyalty of a creature (even allowing it to be killed) because he was afraid for himself. And the ending was a strong one, in which the somewhat cowardly main character redeemed himself somewhat when his dying new prophet begged for at least one sign before he died, and the "god" sent a bolt and split the old prophet in half.
Don't know if this rings any bells in anyone's memory, but obviously this was a strong story for me to have remembered it after all these years (either that, or maybe I just have a weak mind).