I highly recommend the Lupicia shop in Roppongi (4-2-35 Roppongi,
Minato-ku, Tokyo), with a superior selection of Japanese teas, Indian
blacks, and Taiwan wulongs. One can also sit and drink tea here.
There are other branches in other parts of town.

Also recommended is the combination cafe/shop in Takashimaya just
south of Shinjuku station. The fifth floor I think.

There is also specialty Chinese Tea Shop near Chinese embassy in
Roppongi and another good one along Omotesando in Harajuku. Go south
down the hill from Omotesando station, and it is on the left side of
the road about 150m before the main intersection (the one with the
Gap).