Is it possible to change your Deity?
 

Not sure if it was possible because I never thought to do it but can you change your Deity with a quest or something. Mainly can a Caz Troll shaman change to Innoruuk?

no, you can not :(

There is a quest for it, but it's a rough one.

1. Store all of your Cazic shaman's gear on an alt or with a friend
2. Delete your Cazic-Thule worshipping character
3. Quickly (before anyone takes the name) re-create the character but worship Innoruk
4. Move the gear back
5. Level back up

It sounds bad, but as long as long as you do it before you are too high level it's actually easier than some quests on this server.

Doesn't this quest cause a bug where you can no longer be seen on /who <name> ?

I was really expecting something along the lines of
http://i.imgur.com/h2BuJwR.jpg

I suppose if you lose your faith.

Never heard of that, but depending on your perspective I guess that could be considered a feature and not a bug ;)

No

would be a cool custom quest if it was possible.

:) Totally, but I think it'd have to be multiple custom quests to do it right. I shudder at the thought of what Cazic Thule or Innothule would require of you to join their faith ...