I don't know where to start exactly, but I tried to pick in along the second verse of the riddle. (So I understand my answer is either totally wrong or incomplete)
Go along until you hit
A shining water line.
Move along a line until you reach a station on the Tozai line.
Then head upon to the first
And turn around with glee,
Don't forget to go on to
The algae, algae line.
Along the Tozai line, move until you reach the Otemachi station. This is the answer from the first riddle ("Head upon to the first"). Now continue along the Chiyoda line, as this has a colour similar to algae.
From there you go until you hit
Upon a certain Diet
Some research shows that the National Diet Building is near Hibiya. So you follow the Chiyoda line until there.
And then along the Astoria line
Through 3 more stations plus.
The Astoria line bares the same colour code as the Ginza line. So from Hibiya you go to Ginza and then add 3 more stations to arrive at Mitsukoshimae.