If you go Pazuzu Pazuzu Pazuzu, You can get a wish to get a candle of invocation to get some more wishes. With those wishes you could wish to duplicate PaO Twice to make yourself into a dog.
You'd be using Pun-Puns method to become a dog, not a sahruuk, but it would work.
It is classified as TO though.
(You should probably become a blink dog though, as you get the intelligence of the creature with PaO, and having int 2 sucks)
Another option is to use the wish to get an item (A dogs collar perhaps) that can cast Magic Jar at any time. You'd have to play something small, like a Jermlaine that the dog could carry in some sort of backpack. The bad thing is you would have the hit points of an ordinary dog, so unless it is your animal companion you are possessing you would suck. However, whenever your dog dies you just need to find a new one you can possess, with magic jar that is sort of simple.
The last option is finding a way of getting true mind shift.