As others have said, there are many ways to structure the core meetings in a Scrum environment. I am a Product Owner and the overall manager of the development group (among others) although there is a "team lead" between me and the developers (he is also the Scrum Master).
As Product Owner, I am present for all Sprint Retrospectives. It is important for me to be there because when the team discusses the Three Questions (what worked well, what didn't work well, what should we start doing), I need to listen and ensure that I know what to continue doing that worked well, what to change if something didn't work well and it's my fault, and to ensure that I am aware of something that will be starting (if I can help the Scrum Master facilitate the change, or adjust my expectations, etc).
So, in my organization, the answer to "Should Product Owner be present in all retrospectives" is yes because it adds to the continue trust-building and overall product/team cohesiveness.
That may or may not be the case in other organizations. In the situation you are entering, even though there are many ways to do Scrum, I am going to venture to guess that the team is not very cohesive and probably does not function as well as it could, because of the lack of retrospectives and a previous authoritative Scrum Master. The latter is a big problem; a Scrum Master is to be a facilitator and a trust-builder rather than a task-master.
Given that your team is likely not used to working in a trusted, open, honest environment where problems can be aired and solutions found, your concern that "people will not behave naturally hiding some information for political reasons" is valid but that would be independent of the product owner being there. In other words, without strong facilitation and understanding that the retrospective is ultimately for them, I doubt that the Product Owner being there or not would change the likelihood that the team responds honestly and openly.
I agree with Zsolt's statement that there's likely a good reason the Product Owner wants to be at this retrospective -- and the change of Scrum Masters is a good hint as to why. However, even if there wasn't a good reason, to my mind he should be there anyway.
You have a great opportunity to reset the way that the team functions -- good luck!