Avocado has a lot of fiber too. Cellulose is not digestible by humans, all insoluable fiber like skins to fruits will pass thru system.
The fact you get it passed thru your system so quickly (over night) that sounds like you don't have issues.
Do you do any fermented foods (coconut kefir, probiotics ) ? I would think if you are eating little to no vegetation you would need plenty of bacteria to make stools. Raw meats (sushi etc...) or raw eggs help the bacteria count some too.
I'm not sure then what you meant by the stool part of your diet is a problem? Do you not have stools? Or are you constipated (making stools but difficult to get out?). Rock in your stomach? Having to use laxative to go Etc... Please explain. There is no such thing as TMI when we are trying to figure out our health.
A side note- most protein is absorbed by the body leavening about 3% of the quantity for ash to be expelled.