However, if there is concrete evidence that the Higgs does not exist it does make gravity/mass a wide open field.
Not gravity - it is a common misconception that the Higgs has anything to do with the vast majority of gravitational mass. The Higgs is what gives rise to the non-zero rest-masses of the various particles. But rest-mass is an almost negligible contribution to the total mass of gravitating objects.
Yes, the origin of the non-zero rest masses becomes open again if the Higgs mechanism is not responsible. But it will almost certainly be something similar, if not specifically the Higgs then some equiavlent or condensate (possibly from some new phsyics, which is why it would be exciting); there are too many constraints from the physics we do know for it to be a completely open question.
Also, finding the Higgs is no barrier to investigating new physics. On the contrary, the Stanard Model with Higgs is still the most bizarre hodge-podge and is a blatent sign that it is merely an effective theory of some deeper physics.