18500
I think that there are a lot of societal influences with regard to how to
begin addressing a Japanese man with his first names. Please put the societal
issue aside and just consider the linguistics of this scenario.

  * Both the Japanese and American are speaking in Japanese.
  * Both the Japanese and American are men. 
  * In formal and informal settings, a Japanese addresses me using my first name.
  * I address the Japanese using his last name.
  * During the first few weeks / months of getting to know him, he uses my first name and I use his last name. I can't remember how it happened, but I've been speaking to some Japanese men using their first names for awhile.
  * I prefer using his first name if I consider him a close friend and if he has no problem with it. But, in the presence of another Japanese person, I would never say his first name. 

When I think the time is right (which is not this question), how would I
express this thought in Japanese? The context is an American saying it to a
Japanese.

> Hey Tanaka-san. Is it cool If I start using your first names?

I would say something like

> 悪いけれども、これから、下のお名前を使わせて頂いても、宜しいんですか？

Is that ok? I am sure it sounds very unnatural, but even asking to use his
first name is unnatural. So, what should I say?

By the way, my observations are that, even when best of buddies, Japanese men
always address each other using last names. And, the norms for addressing
Japanese women with first names are completely different.
CC BY-SA 3.0
2014-08-30T16:09:46.343
18492
2014-09-02T05:08:28.510
2014-09-02T05:08:28.510
6840
4835
question
translation
How to say "let's start using our first names when we talk?"
Yours is good but the よろしいんですか part (which would mean "Are you saying you
allow me to use your first name?") should be よろしいですか (though いいですか or
よろしいでしょうか are better IMO).

That said, 下の名前で呼ぶのはどうでしょうか？ is probablly closer to what you want to say.
CC BY-SA 3.0
2014-08-30T22:58:08.443
18496
2014-08-30T22:58:08.443
4092
18492
answer
How about:

> ([今度]{こんど}から)[下]{した}の[名前]{なまえ}で[呼]{よ}んでもいいですか。(a little casual)  
>  下の(お)名前で呼ばせてもらってもいいですか。/[構]{かま}いませんか。(more polite)  
>  下のお名前で呼ばせていただいてもいいでしょうか。/よろしいでしょうか。(even more polite)

etc...
CC BY-SA 3.0
2014-08-31T03:34:08.127
18500
2014-09-01T01:28:16.513
2014-09-01T01:28:16.513
18492
answer