I think there are two key points to making such a system work:
1. Packaging it in such a way that it's easy to use for non-technical users.
2. There still has to be a mechanism for establishing trust in the public keys registered in such a system.
For one I'd imagine that farmers are doing some amount of work to go from raw "lettuce in the ground" to "one unit of shipment". Once it's a unit of shipment it could have an ID/Bar/QRcode generated that is then scanned with a handheld scanner that has its own keypair. The scanners keypair would be registered with the farm and so the farm would either explicitly sign off on the package or implicitly have signed that scanners pair as trusted by the farm. So a farmer and farmstaff wouldn't need any technical know how beyond operating a scanner. Depending on the farm adding such a granular tracking system may or may not be easy to implement.
For two, I can see two options. Walmart could verify every step of the chain themselves and register/receive the public key for each step in the chain. (So a farm would register with Walmart as a verified producer, a shipping company would register, etc). Or each step of the change could make a binary decision to trust the step before it and apply pressure down chain to resolve issues, since theoretically each step could fabricate the entire chain before passing it off. In this scenario, Walmart would go to the shipping company and say "E. Coli was detected in Shipment X. We no longer want to be sourced produce from Producer Y. The shipping company then takes this into account when sourcing produce, or else Walmart discontinues business with them.
I think the big benefit is by having an associated public key, you can verify the claimed identity of any agent in the chain and build trust in that agent over time. You could keep popping up disposable proxy farms, but Walmart/Shipping provider/X doesn't have any reason to trust your proxy farm's shipments; you have to establish trust either directly with a buyer of your produce, or establish trust over time as a commodity provider. As you build trust you can probably get better prices.
I'm by no means a blockchain advocate or a supply chain manager of any kind, just doing a thought experiment of how blockchains might be effectively applied in such a scenario. There very well might be better solutions, but I think at the very least a blockchain presents an interesting or novel solution.
Just thinking through, you could also create a sort of "doubly linked list" and include who custody was given to as part of each block, so a farmer is signing a claim of who they gave their produce to.
{Farm A produced unit of Lettuce X, Given to Shipper B, }[Farm A signed]