Finding an Apartment first day in Tokyo?

I'm going to be moving to Minato, Tokyo in May to continue my career of tattooing; hopefully this will be my last move. But since the only family I have in Japan is down in Shikoku, I don't really think I'd want to go and travel from Shikoku to Tokyo everyday.
I know that I have to pay six months of income to the person who I rent from before getting a key, but how hard is it to find an apartment the first full day you are in Japan?.

I recommend to find your apartment before you even leave for Japan. Thanks to the internet, it is easier than ever before. Many apartments do not require such huge initial move-in payments. More details are here:
http://www.japan-guide.com/e/e2200.html

Good luck finding an apartment in Minato-ku. It cost an arm and a leg and then some just for a hole in the wall.

Minato-ku is probably the most expensive area of Tokyo to live in- the very centre and fashionable. You would have to be very well-funded to live there. Only about 15- 20 minutes away by subway you would pay a quarter of the rent.

I have a position at the University of Tokyo. They provided me with a hotel for my first week here. My generous Japanese friend took me to a rental agency (I don't speak Japanese well) and we found an apartment within about 4 hours.

However, I am not picky, and all I wanted was a place close enough to walk to the University. My place is tiny and cheap, and it's perfect for me.

As others have posted, you might want to consider finding a place outside of Minato-ku. It's super easy to travel on the subways and trains. It's totally possible to find an apartment within a day.