When I was in Osaka about a year ago, I went to the Kansei-kiin. Initially I had problems to get a game. I declared myself as 5 kyu, and they said they don't have an opponent, so I should wait a bit. I then watched the game of two Americans, and they told me that as an European 5 kyu I should at least say that I'm Japanese shodan, and if you're weaker than shodan, it's hard to get a game in the big clubs. Around that time, an opponent appeared (I think she was 4 kyu), and was immediately scared away because I'm so strong
. Later I got two games against a 3 dan. He was quite a bit stronger than me, and he seemed very reserved. My impression was that he just played me to be polite, but the Americans said if that were the case, he wouldn't have offered a second game.One of the Americans later introduced me to a small go club, and I went to that club a few times. That was a lot better, and there was a very strong player (7-dan, supposedly takes only 2H from pros), and he was willing to play handicap games with me. I don't speak Japanese and the Japanese players spoke just a little bit English, so communication was a bit difficult, but it was not really a problem. I seemed to really have surprised him with my play, the American said winning one game against him just means he underestimated me, but he never saw someone win a second game (but of course in the third game I was severely trashed at one less handicap
). At the end, he came to the conclusion that I'm "at least 3-dan" 
.Of course I had the advantage of being introduced by someone they already knew...
For finding go clubs, look out on the street for the Japanese characters for go (囲碁). There are really a lot of them, in some areas every few streets, you just need to actively look for them. For example, that's how I found a small club in Kyoto. I didn't really plan to go to a go club, I more or less stumbled over it. I just was walking from one tourist spot to the next, saw the sign, and just walked in. This time, I declared myself as "2 dan or 3 dan". I got two games, both opponents were more or less my strength. Unfortunately, I didn't have enough time to stick around.
Oh, and before I forget: You'll probably have to pay for playing, even in the small clubs. But it's not really expensive (I don't remember the exact price, but I remember at the Kansei-kiin it depended on my rank).
TL/DR:
- Find a small go club, they are a lot better than the "big" ones at Kansei-kiin or Nihon-kiin.
- To easily get games, be at least Japanese shodan (as KGS 2k that's probably still a little bit sandbagging).
All Japanese that I played with were genuinely surprised that a foreigner could be so "strong" at go, that seemed to turn me into some kind of attraction
