the version I learnt the phrase from had the end of the chain as
- oh we should paint it
- we need a paintbrush
- I hear yak hair makes the best paintbrushes
- here I am, shaving a yak
made more sense than the examples given in the op
So yak shaving comes after bike shedding?
Internet Search Thing now tells me sable (for soft brushes) and hog hair (for wire-like brushes) is the best hair for this purpose. Oxen occasionally show up. Yaks nowhere to be found.
Coincidentally, this is also the first time I'm hearing about sable.