It's a known fact that gifted children challange authority and generally do find nursery difficult.
Um no, they generally don't, so that's not a "fact" though it is a widely held belief. Sometimes the problem is that because they seem advanced adults expect them to be more mature in every way when mostly they are simply four years old. Sometimes they are advanced in some ways but actually behind in others. It can be hard to see that the child who is already speaking in whole complex sentences on abstract topics actually has very limited ability to interpret non-verbal communication and can't tell the difference between a firm voice and an angry voice; or that a child prefers adult company to other children because the adult will allow him to control the conversation and keep it within his own comfort zone whereas other children wont; or that a child insists on everyone following the rules not because he is so aware of the adult world but because he sees the world in black and white and can't cope with the shades of grey that other kids manage naturally.
The behaviour is good if you use a different stategy i.e. It took you 5 seconds to put than in the bin last time, let's see if you can do it in less.
That reminds me a bit of Charlotte Moore's "but he can do it, he just doesn't want to" and the psyschologist's response "that's the point - at his age he should want to". Like you I had to think of different communication strategies to get my DS to do what I wanted - but my DS has Asperger's. My friends whose children are simply gifted didn't have to find special ways to get their kids to do what they were told.
the educational psychologist said although some traits, he isnt autistic
They really can't "rule out" an ASC at four years old, certainly not the higher-functioning versions. The most they can say is that he is not showing enough signs to indicate an ASC right now but that can change as his development progresses and especially if he already shows traits. Your own criterion "Desire to organize people/things through games or complex schemas" sounds a lot more like high-functioning autism than giftedness. It's the application of what he's good at - complex abstract schemas - to what he may be bad at - social communcations.
The emotional needs of any child at any intellectual level can be different from the norm. That has nothing to do with being gifted or not. But I agree it is useful to have schools that will support both the advanced intellect and the weak social/emotional/communication skills. The difficulty we had with DS was that local special schools could support his disabilities but not his intellect.
Kids of young ages don't change that much that dates affect studies so much.
But the interpretation and classification of children's behaviour has changed a lot. No-one in the UK had even heard of Asperger's Syndrome until Lorna Wing started her work on it in the late 1970s / early 1980s.
A lot of his conversations are one sided about a topic of his interest,
That is common in with Asperger's. So if things don't improve I really would get him re-assessed when he's a bit older, possibly by a SALT.