I've seen gluten-free masa harina in both the Zhongxiao Fuxing City Super, and the Tianmu Sogo one (near Zhishan MRT Station). I first saw it there a few months ago I guess, and it's remained there, so it's as regular as an imported product ever is here (i.e. it may disappear tomorrow).
I'm not sure what difference there is, if any, between gluten-free masa harina and the "regular" masa harina also sold by Bob's Red Mill (not available in Taiwan, as far as I can tell). A brief Google search suggests the main difference is the gluten-free stuff is processed in a facility that doesn't process other products with gluten, so I guess the gluten-free masa harina is just as good as the regular stuff - if, that is, you're looking for masa harina, rather than the "wet masa" (?) that Icon is talking about.
Note that masa harina is also quite easy to get from iHerb (i.e. shipped from North America), as are basically all Bob's Red Mill products. That usually seems to wind up cheaper than buying the stuff here, depending of course on what you're ordering and how the shipping charges even out.
Canned tomatillos, on the other hand, seem to have disappeared. I haven't seen any in a few years now.