Specifically, I stepped in canine fecal matter with deep-treaded hiking boots. The process to remove the foreign substance was arduous and tiresome. Hot water, dish soap and the use of brushes did the job, but then every tool or brush that was used in the process needed to be cleaned and sanitized.
I would soak the soles of your boot in a highly-concentrated solution of biological washing powder and warm water. You would only need enough water to cover the soles of your boot, nothing deeper. You would probably need two or three scoops of powder.
The biological washing powder should literally eat away at the feces and hopefully remove it entirely. I would imagine you would need to soak the boots overnight at the least.
I've not tried this myself, but using biological washing powder to unblock toilets is a well known life-hack. I see no reason you can't apply the same theory to a boot.
Power-wash the soles
The advantage would be that you avoid the manual removal and need for decontamination of the cleaning tools. Power-washing allows use of detergent, which would help get rid of the funk.
You would want a high angle (less powerful) setting so they don't get damaged. The key is positioning them on a stand that will not get knocked over. Wood clamps could be used to hold them down.
I can't speak of this as a fact, but someone told me a long time ago that you can use a hair drier to dry the feces, and then use a small stick or a toothpick to remove the feces once they are completely dried out.
I did a quick search in Google, and found this - apparently you can get rid of the feces by putting your shoe in the freezer, and then removing the crap out of it with a pencil (!). It doesn't say anywhere that you have to discard the pencil, but I would highly recommend that :)
Use a nozzle shower (in a shower stall or in a bathtub) or a bidet shower (if you don't at home, find the toilet in the nearest hotel where they could have it), set it to cold with high pressure and redirect a water stream at a safe angle inside a shower cabin or keep low over the toilet seat. Apply soap when required. In this process you don't need to use any tools to be cleaned and sanitised, only the area which you eventually left dirty, so use the toilet paper to clean as well as to wipe your shoe.