I would definitely start tethering him to your side with a 6 foot lead when he is not crated or in a playpen with appropriate toys. Eating poop is pretty common with puppies, but I would make sure you are watching him closely when he goes outside. Be ready to reward and redirect immediately after he poops - don't even give him time to sniff it! It's much harder to break after he's made a habit of eating it, so don't let him start that habit in the first place
Instead of yelling "NO" try just redirecting onto something else. I'll say "Hey!" or "Over here!" in a happy tone to get my puppy's attention so that I can make his environment and his (guided) choices as positive as possible. Show him that his toys are much more interesting and most importantly, make sure you're not just stuffing the toy in his mouth and expecting him to play with it - interact with him, play a fun game as a reward for him choosing the toy over the poop/shoe/ thing he wants to chew on.