Is the Higgs mechanism a fundamental interaction of the same standing as the strong, weak and electromagnetic interactions? If not, is it mediated by the weak interaction? It seems that all the massive particles participate in the weak interaction, and the massless ones do not, but this might just be a coincidence.
It's a terminological question. Most of the time, the fundamental interactions are only those that are caused by virtual $j=1$ or $j=2$ bosons, i.e. gauge bosons and gravitons. The Higgs mechanism – the proocess that gives W-bosons, Z-bosons, and others masses – isn't really caused by virtual $j=1$ or $j=2$ bosons.
In fact, in contrast with naive expectations, it isn't caused by virtual $j=0$ Higgs bosons, either. There are no real Higgs bosons in the vacuum; and when we calculate the mass of the W-bosons or Z-bosons or leptons or quarks, there are actually no virtual Higgs bosons involved, either.
A virtual particle has a rather specific meaning; a propagator for this particle must play a role. However, in the Higgs mechanism, no propagator plays any role. So it is not an effect caused by virtual particles. It is not caused by virtual gauge bosons and it is not caused by virtual Higgs bosons, either.
Instead, the Higgs mechanism is caused by the interaction of the Higgs field with the other fields – gauge fields or lepton fields or quark fields – in combination with the nonzero vacuum expectation value of the Higgs field. The nonzero vev of the Higgs field makes the Higgs field unique. No gauge boson or graviton has a nonzero vev in the vacuum – because a nonzero vev of a Lorentz vector or tensor would break the Lorentz invariance. For scalar fields such as the Higgs field, it is possible to have a nonzero vev.
The nonzero vev is a "new idea" that isn't involved in the usual discussion of the four fundamental forces which is why it's not possible to discuss the Higgs mechanism as a special or new example of the four fundamental forces.
The other ingredient that is needed are the interactions of the Higgs with the other fields. The interactions with the W-bosons and Z-bosons are indeed weak interactions. Normally, we would be interpreting this interaction as something that affects the matter particle – the Higgs boson – by the weak force which is mediated by the W-boson and Z-boson fields. However, the influence also goes in the opposite way which is important in the Higgs mechanism.
The Higgs vev also gives masses to fermions. The relevant cubic interaction is known as the Yukawa interaction. It is a new term in the Lagrangian that is closely analogous to the fermions' interactions with the gauge fields. In this sense, we should count the Yukawa interaction as a "new force" aside from the four known fundamental forces. We just don't do it because this terminology would be too divisive when it comes to particles and forces. Each bosonic field is both a source of a force as well as particles and it doesn't make much sense to talk about them in isolation. That's especially the case for the Higgs boson.
Finally, I want to say that the main observable effect – we could say defining effect – of the Higgs mechanism is that it gives or changes the masses of the other particles. But in the terminology of quantum field theory, the masses are caused by mass terms and they're not considered interactions at all: they are bilinear terms while interactions must be at least cubic. The Higgs mechanism is something that can change the interactions – between the Higgs and either gauge fields or fermions – to something that isn't an interaction at all, namely new mass terms for the other particles.
For the latter reason, I would choose to say that the Higgs mechanism itself isn't an interaction at all. The interactions – cubic or higher-order terms – that are needed for the Higgs mechanism to operate are the electroweak interactions between the Higgs and the gauge field; and the Yukawa interactions between the Higgs and fermions. However, we can't say that the Yukawa interactions are the same thing as the Higgs mechanism; they're just one of the ingredients that are needed for the Higgs mechanism to affect fermions. The other key ingredient is the Higgs vev or Higgs condensate. The Higgs vev is kept nonzero because of the Higgs potential – which is a self-interaction of the Higgs field (with itself). The Higgs potential is an interaction (at least the quartic term is) and we could also call it "a new force of Nature" but no one does it because we don't learn anything from this terminology.
So I would prefer to keep the terminology that "forces of Nature" are effects of virtual bosons with spin.