Have all Wolf-Rayet stars evolved off the main-sequence? From what I've read from various sources, Wolf-Rayet stars are massive, evolved stars that typically are the hottest, most luminous stars known. They experience high mass loss, taking their mass from $\sim 100 M_\odot$ to only $\sim 20 M_\odot$. However, Wolf-Rayet stars like R136a1, 2, and 3 are still supermassive, at around $150-220 M_\odot$, and are about only 1 million years old.
Does this mean that these stars already have burned their hydrogen and have evolved off the main sequence, or are these stars still on the main sequence but are classified as WN5h as a result of its high surface temperature and luminosity?
Wolf-Rayet stars have long been a subject of controversy in astronomy. Observationally, they are the class of stars that astronomers identify as being very luminous, having very little hydrogen, and are mostly composed of helium, carbon, nitrogen, and oxygen. This class of stars remained an enigma until the 1980s, when Wolf-Rayet stars started to be considered as the end result of high-mass stellar evolution (due to better modeling and observations, specifically improvements in spectroscopy and better telescopes). Nowadays, WR stars are suspected as the likely stellar progenitor to black holes and high mass neutron stars (depending on the mass and metallicity, i.e. see Heger et al. 2003).

Does this mean that these stars already have burned their hydrogen and have evolved off the main sequence, or are these stars still on the main sequence but are classified as WN5h as a result of its high surface temperature and luminosity?

Regardless of whether you interpret the Wolf-Rayet phenomena as the end result of high-mass stellar evolution, a Wolf-Rayet star is off the main sequence because it is a type of core-helium burning star: it exhausted the hydrogen in its core and thus is not on the main sequence.
Wind mass-loss of Wolf-Rayet stars is strong for their relatively small size. That is, the mass loss rate is actually comparable to that of main sequence O-type stars (the likely stellar progenitor of Wolf-Rayet stars), however the Wolf-Rayet star has smaller radius and smaller radius of gyration than main sequence stars so the comparison becomes complicated. Such mass-loss rates depend on the star's luminosity (and thus mass), as well as the metallicity. The star WR R136a is located in the Tarantula nebula, which is not a high-metallicity environment, meaning the mass-loss rate for this star is not particularly high, which is consistent with it still having such a large mass. Recent analysis of this nebula has actually revealed that the existence of such very high-mass stars might not be as rare a once thought, implying there may be many stars similar to R136a in the cosmos.