Physicists, while knowing very little about it, are sure that something akin to the Higgs field does exist. The Higgs field is an integral component of the currently predominant theory of particle physics called the standard model.
Within the standard model, if the Higgs field did not exist, neither would we. Through their interactions with the Higgs field, various subatomic particles (such as the electron and quarks) become massive. If the Higgs field did not exist, then these particles would have no rest mass whatsoever and, just as photons (which have no rest mass), would fly off at the speed of light. These particles would never be able to form atoms as they would be too busy zipping about at the speed of light.
Even in this crazy Higgs-less world, particles would not be able to exceed the speed of light. That universal speed limit arises from the fabric of the universe known as space-time, whose properties are described extensively in Einstein's special and general theories of relativity. Thus, as you said, the implications on particles' velocities from Einstein's relativity would still apply were there not a Higgs field. If you'd like to read more about the Higgs field I would highly recommend reading Professor Matt Strassler's "Higgs FAQ" as it is an accessible starting point that addresses many common Higgs questions.
(published on 02/08/12)