He's a more complicated and angry Doctor Who. While the Doctor always comes back as an adult, Bob is forced to relive childhood over and over again. Alleviating that tedium may be the primary reason for his egress from continued existence. Unless a mystic tells him that he can die permanently by really wishing himself dead then committing suicide, his only other option is to terminate all human life; specifically all women but killing everyone is easier.
The problem is, on average, he's likely to be desperately poor, fighting for life on subsistence farming with no education or way to get out. Even if he wants to kill everyone, it will be incredibly hard for him to do so after starting so low on the socioeconomic ladder (though not impossible. Some of the most destructive people in history started out very low on the ladder. Genghis Khan is a good example.)
Poor, all the time
The odds that Bob will be born in anything other than poverty is vanishing small. 80% of the world lives on less than $10/day. Over several life times he'll likely accumulate more wisdom and knowledge but the growth curve for formal knowledge will remain pretty flat, just because there's so little formal education to be had. For example, literacy rates in India for rural populations up until ~1950 were less than 20%. Poor countries don't have libraries and poor people don't have the time to go to them. Africa is 65% literate as of 2015. Even with the modern advent of the information riches available from the Internet, he's going to have trouble even getting access to the Internet as Africa has an internet market penetration rate of only 27% at the end of 2014. Asia isn't much better at 35%. Sure, if you live in a poor portion of the world, you could get access to the Internet but doing so is expensive, distant and you have fields to tend.
(Let's make an important distinction between book learning and street learning. Bob will have minimal formal book education because poverty. But he will have life times of experience with people. He will be an exceptionally savvy negotiator and opportunist, if he wants to be.)
In short, if you don't live in Europe or North America before the 1960s or 1970s, there a very good chance that your parents and your forebearers could not read. The amount of math, science and local language training available to you is vanishingly small and expensive to gain.
Childhood
This is going to be the hardest period for him, every single time. Assuming he doesn't lose any cognitive ability at birth, the act of being born is going to be painful. Neglect and child abuse are the highest in children between birth and three years so he'll have to struggle with that. If he learns some psychology then the following may drop out of his mouth:
This isn't my fault, Dad. Get your act together. Go to therapy/shaman/medicine man. Don't
take out your daddy issues and failed childhood on me. I didn't make
us poor. I didn't make you drunk.
Since childhood is where Bob spends most of this time (and it happens every single time, regardless of lifespan), he may pick up and keep some childish attributes.
Having a mind so out of sync with a body is going to be really weird. As a child he will remember sex but not have the body to do anything about it. Puberty will be an exercise in pain/frustration as he knows what to do but his body can't match or just isn't strong enough yet. (I can't imagine reliving puberty over and over and over again.) But, it may actually be easier for him because most or all the issues that a teenager needs to figure out for themselves, Bob has already figured out and can just get on with whatever it was he wants.
Life as a woman
After spending time as a woman, I think Bob would have a completely different appreciation for women and how they should be treated. I don't know how he would cope with the sheer quantity of sexual assault and abuse he'd experience as a woman....and he can't die to forget.
Mastery of many languages
Assuming that the brain plasticity of each new body helps him learn a new language and each language stays with him, then in a hundred years or so he'll be able to go most anywhere in the world and communicate handily.
Potential to be an amazing lover because he'll have lots of experience and know what to do emotionally and physically.
Government Bob
Given that 80% of Bob's lives are as a desperately poor person, he won't be superficially worth much to anyone. Poor people are (unfortunately) very common so asking Bob about 20 life times spent slaving away under the hot sun isn't useful.
Mental Illness
If he gains some kind of mental imbalance such as PTSD (which is very likely as he's on balance going to come back poor in the Third World) because of a violent experience then those memories may stay with him for a very long time. If, for example, he fought in WW2 as a Russian soldier at Stalingrad, he's going to remember the mountains of corpses...but he will remember them as a child of 4. No parent on the planet is prepared for a child that vividly remembers events from decades ago with a degree of detail attainable only by someone who lived it.
Sociopathy is another characteristic that he is very likely to pick up. With all the evil that is done to him over the many lifetimes and childhoods, empathy may be something he really struggles to get and keep. Compound this with a very real "otherness" brought about by his very long life experience, even as a small child, social isolation is going to be a really problem.
Bob may have also lived long enough that he remembers the really inhumane periods of history like the Spanish Inquisition and given how different he probably is, will have suffered at the hands of said Inquisition.
As a young girl, the horror of marriage to a man many times his age... The mind boggles.
Detection
After one or two lives he's going to think like an old person from a very young age. His peers will certainly notice. If he retains the education gained in typical First World schools, then he may pass on to post-secondary education incredibly young.
Personality
All this pain and suffering will either make him an incredibly kind person or an incredibly cruel person, depending on how his initial personality was.
If he's not stark raving mad from a young age (or just appears stark raving mad), he's stands a high chance to have a mental disorder very similar to psychopathy (the genetic variant of the "lack of empathy" disorder) because everyone he's ever known is either irrevocably far away or long dead. And as seems to be common for those who live forever, the pain of continued loss decreases inclination to form new social connections.
Famous Last Words
His most frequent words on death might be "Aw hell. This is really gonna hurt." Everyone will think he's talking about dying but he's really talking about being pushed out the birth canal.