Locomotion gaits are fundamental for control of soft terrestrial robots. However, synthesis of these gaits is challenging due to modeling of robot-environment interaction and lack of a mathematical framework. This work presents an environment-centric, data-driven and fault-tolerant probabilistic Model-Free Control (pMFC) framework that allows for soft multi-limb robots to learn from their environment and synthesize diverse sets of locomotion gaits for realizing open-loop control. Here, discretization of factors dominating robot-environment interactions enables an environment-specific graphical representation where the edges encode experimental locomotion data corresponding to the robot motion primitives. In this graph, locomotion gaits are defined as simple cycles that are transformation invariant, i.e., the locomotion is independent of the starting vertex of these periodic cycles. Gait synthesis, the problem of finding optimal locomotion gaits for a given substrate, is formulated as Binary Integer Linear Programming (BILP) problems with a linearized cost function, linear constraints, and iterative simple cycle detection. Experimentally, gaits are synthesized for varying robot-environment interactions. Variables include robot morphology - three-limb and four-limb robots, TerreSoRo-III and TerreSoRo-IV; substrate - rubber mat, whiteboard and carpet; and actuator functionality - simulated loss of robot limb actuation. On an average, gait synthesis improves the translation and rotation speeds by 82% and 97% respectively. The results highlight that data-driven methods are vital to soft robot locomotion control due to the significant influence of unexpected asymmetries in the system and the dependence of optimal gait sequences on the experimental robot-environment interaction.