Every Newbie should start with playing Japan first IMO.
Most of the reasons given here about why they should play an Allied country or not Germany are precisely why they should play Japan.
My rationale may be significantly different than yours….because my starting point is to give the newbie a first game enjoyable experience…so that they will play again. Everything else is secondary.
Now, the Allies require coordination and there are three of them. IMO, there is absolutely nothing worse than your so called teammates telling you what to do and effectively making all your moves for you. This is not at all a fun way to learn a game like A&A. The other players should help you with rules, maybe even discuss the relative merits of your plan…but not in detail and not so that it is their plan and not the newbies plan. The newbie needs to be in the driver seat…he makes the overall decisions…he explores what seems to make sense. You should restrict your advice to when it is requested and/or only when a clear game losing move is about to be made…prolong the basic fun and game for him…but make sure he is in the game…not just observing.
So, Japan. They can be played independent of Germany, with little need for early cooperation. They start with a lot of pieces. They have both land and naval forces that should last at least a few turns. They have lots of airpower. Even a newbie will advance and gain in Asia. Their fleet can try numerous things in the Pacific. They are an island nation with a good starting position. It is almost impossible to screw things up so bad that you cannot have some victories and fun. They are not really subject to potentially devasting first turns and real early collapse. They will be engaged in combat almost certainly every turn, and likely on multiple fronts…but none are instant game losers. They have enough options that they can try all sorts of strange and wonderful things, that will also bring back a smile to your face as you realize their naivete. Because of all these factors, you can be guaranteed that Japan introduces them to all the pieces, all the rules, multiple fronts, many combats, and lots of fun. You can still have at least 5 turns of reasonable gaming experience, and you may even be inspired to respond with some wacko Allied moves…just to keep it fresh and prolong the inevitable.
With a newbie it should always be about getting them to enjoy the game.
Thus, I submit that Japan is by far the best choice.