Killing him altogether seems pretty epic level, like level 25+, given that he's a deity. (But your DM could be ballsier than me, lol. Killing an aspect of him to weaken him for a bit seems more my speed.)

Alternatively you could try shifting goblin worship in localized communities to another deity. Maybe someone like Kikanuti (since I imagine getting them to worship someone like Tymora immediately might be too much of a jump?) or some other goblin. (Were Konsi to be more arrogant, I'd suggest her. =P) Kill him slowly, death by 1000 cuts of lost faith style.