You state:
But if the Higgs field is what gives mass, then these particles could not have existed with those masses, nor any mass of any value, before they began interacting with the Higgs field.
The basic misunderstanding is that particles interact with fields. The fields are like a coordinate system on which one can model with quantum field theory the behavior of particles.
All the particles in the table of the standard model are represented by a field. The field mathematically is represented by the plane wave solution of the corresponding particle, Dirac for fermions, Klein Gordon for bosons, and covers all space time. The electron field covers all space time the same is true as well for all particle fields in the table, including the Higgs.
Fields do not interact in quantum field theory, fields are acted upon by creation and annihilation operators which manifest interactions between particles.
Energy exchanges happen between particles , not between fields.
The Higgs field acted upon by a creation operator will describe the Higgs boson interaction or decay , not the Higgs field.
In general the energy is input coming with the four vectors of the particles , the fields do not have a four vector describing them, just a quantum mechanical wavefunction.
The popularized image of an electron gaining mass because it is wading through the Higgs field is misleading. Electrons and the rest of particles in the table gained their mass at the symmetry breaking time in the model of the universe, and have this fixed mass ever since.