Going through the different parts of this question, here are the answers I found:
Are male and female brains different?
Yes. While searching around the internet I found a handfuls of websites with nearly all of them pointed to the same set of differences. I also found various references to studies that I was unable to access (or, admittedly, understand.) But I did find the article Are There Differences between the Brains of Males and Females? which I consider well presented, written and referenced. The article was by Renato M.E. Sabbatini and appears legit. The references are at the bottom of that page and seem to be from 1999 and before.
The main takeaways:
One of the most interesting differences appear in the way men and women estimate time, judge speed of things, carry out mental mathematical calculations, orient in space and visualize objects in three dimensions, etc. In all these tasks, women and men are strikingly different, as they are too in the way their brains process language.
On the other hand, women are better than men in human relations, recognizing emotional overtones in others and in language, emotional and artistic expressiveness, esthetic appreciation, verbal language and carrying out detailed and pre-planned tasks. For example, women generally can recall lists of words or paragraphs of text better than men.
These areas matchup with the other sites I found. Also, apparently male brains are physically larger (but this has no notable impact on intelligence.)
How are the differences measured?
Working from the same article above, the measurable differences used to be behavioral. People watched men and women do things and recorded the differences. More recently, they get to study the volume of certain areas of the brain; use functional imaging to determine brain activity during different tasks; and studying the brains of the dead.
Most of these methods were used when determining the above paragraphs of differences. The article details different methods used and provides example studies with their conclusions. Two such examples (emphasis added):
In another research, a group from the University of Cincinnati, USA, Canada, presented morphological evidence that while men have more neurons in the cerebral cortex, women have a more developed neuropil, or the space between cell bodies, which contains synapses, dendrites and axons, and allows for communication among neurons (8). According to Dr. Gabrielle de Courten-Myers, this research may explain why women are more prone to dementia (such as Alzheimer's disease) than men, because although both may lose the same number of neurons due to the disease, "in males, the functional reserve may be greater as a larger number of nerve cells are present, which could prevent some of the functional losses."
Although most of the anatomical and functional studies done so far have focused on the cerebral cortex, which is responsible for the higher intellectual and cognitive functions of the brain, other researchers, such as Dr. Simon LeVay, have shown that there are gender differences in more primitive parts of the brain, such as the hypothalamus, where most of the basic functions of life are controlled, including hormonal control via the pituitary gland.
Do the differences in the male and female brains alter gender identity?
A study on 14 infants born with cloacal exstrophy suggests that social impact alone may not completely override what we consider gender identity. Cloacal exstrophy is a horrible anatomical defect that involves severe complications to handfuls of different organs. Among the affected are both male and female genitalia. After birth, "the trend had been to surgically reassign males with cloacal exstrophy as females by removing the testes and constructing labia." The children were then raised as female.
The study included 16 subjects (emphasis added):
Of their 16 affected subjects, 14 had been reassigned female at birth. At follow-up, between ages 5 to 12, 8 of those reassigned female now identified as boys. The children and their parents completed a battery of questionnaires assessing psychosexual development, sexual identity, and gendered behavior. Follow-up assessments were done at least annually ranging from 34 to 98 months follow-up. All of the subject had moderate-to-marked male-typical attitudes and interests. The two children reared as males continued to identify as males. Of the 14 reassigned female at birth, five still persistently identified as girls, four spontaneously declared a male identity, and four chose to identify as boys after told that they were born male. Reiner and Gearhart note, in passing, that none of their genetically female patients with cloacal exstrophy demonstrated atypical gendered behavior or gender uncertainty.
How young can differences be measured?
The Sabbatini article only offers this note:
However, gender differences are already apparent from just a few months after birth, when social influence is still small.
More searching led me to a completely different article responding to the question, "Are there actually significant differences between a girl's brain and a boy's brain?" Unfortunately, the site is National Association for Single Sex Education, so they have some invested interest in this material. The references seem solid, however, so I will include the main points anyway (emphasis original):
The most profound difference between girls and boys is not in any brain structure per se, but rather in the sequence of development of the various brain regions. The different regions of the brain develop in a different SEQUENCE in girls compared with boys -- this is the key insight from recent research in brain development.
[Harriet Hanlon and her associates at Virginia Tech] found that while the areas of the brain involved in language and fine motor skills mature about six years earlier in girls than in boys, the areas of the brain involved in targeting and spatial memory mature about four years earlier in boys than in girls.
The age ranges relevant here drift from 8 to 11 to as young as 5. This last blurb pushes that even earlier:
On the other hand, researchers at Wellesley College found that 3-year-old girls could interpret facial expressions as well or better than 5-year-old boys could.
So, while I wasn't able to find something directly mentioning infants (other than one site debunking brain size as an identifier), it seems logical that more and more differences will be discovered between the male and female brain, some of which will probably be noticeable at birth.
Summary and conclusion
Male and female brains are different. The differences are measurable through methods that involve the actual brain instead of just categorizing behavior. In addition, that behavior pushed through social efforts to subvert gender identity in at least one study.
The differences between the male and female brain can be noticed in schoolchildren. Specifically, their abilities to process information of certain types. These differences appear to be mostly behaviorally studied but the edge of where those studies are is continually creeping toward infancy.
To directly answer your questions:
I want to argue that this logic is flawed - since identity is product of the brain and not the sex organs. So the question becomes: is there any evidence to support that?
Yes. There is evidence to support that gender identity is based on the physical brain (and its gender) and not merely socially assigned gender roles.
For a bonus question: If there really is such a difference, can it be measured in new-borns?
I wasn't able to find a specific reference to an observable difference in newborns but strongly suspect that such a difference exists based on the articles and studies I was able to find. Most of these studies appear to be focusing on overall differences.
Now, I seem to remember and old science TV show which argued that there are physiological differences between male and female brains and that in trans genders you really do find a female brain inside a male body (for example).
None of the articles I read even mentioned this topic. I suspect the problem here is just that of definition: Is sex or gender based on genitalia or neurology? It would make sense to pick one and work from there.
But regardless of the terms, there have been documented cases of people being born with both sets of genitalia. However you classify their body, the idea that their brain is either male or female (or both?) would assume that the brain is in a body that doesn't gender match. The topic is that of intersex.
That being said, an otherwise normally male brain in an otherwise normally female body is not quite a certainty based on the information I found. Most of the studies seem to be identifying male or female and then studying the brain. What you are looking for is a way to determine if a particular brain is male or female. That seems likely in the future. It also seems likely that people will be born with brains outside of the typical male/female definitions. Considering the varying intersex examples, it seems reasonable to think that your brain could be gender swapped. But I suspect we need to wait awhile for conformation.