You cant change characters role, if he is ambassador, he cant be a spy.
As for selecting another new leader, you cant. Dude, its Democracy)) only your population can elect the new one, not you)
I didn't think I could just choose a new leader, but I hoped I could at least force an election. The leader I started with has the Disliked trait, so it's currently resulting in -20% happiness to all my citizens.
As Ralzakark said, push the big button that says DISMISS. You'll get a new leader after that. You can dismiss any character you want, but only leaders get replaced immediately. After that there is a small waiting period while your government adjusts. Then, if that leader also sucks, you can boot him as well.