Since you want a character at the end of the day, lets exclude all the various interpretations that would make the character unplayable. As others have said, it comes down to what a soul means after that is said and done. It can't be persona and memory, because then you don't have a character, but the following ideas might be interesting:

- The soul is a vote. Each person gets one say as to what cosmic forces win the day at the end of time, as well as the current disposition of things in the universe. If there are more evil people, their souls make evil stronger. Because this character lacks a soul, the divine are completely unconcerned with them (and perhaps cannot even see them) - their vote has already been cast and there's no taking it back. This could also have implications for fate, if such a thing is important in the campaign: no soul means no fated role left to play, so anything they do 'breaks' the divine plan somehow. The character's personality might not be strongly affected by this, but there could be subtle things: they are incapable of faith, lack a visceral moral response (all their morality is intellectual, not based on feeling), etc.

- The soul is a connection to something. This idea would have souls being like some sort of link to a collective (and ancestral) consciousness of the world. Hunches, intuition, coincidence, premonitions, and so on all stem from people subtly learning from the soul-link. The character sometimes is just blank on things that people normally are very intuitive about. They can't tell when people are looking at them, their long-term memory is more limited (because everyone else can lean on ancestral memory), etc.

- The soul is the creative part. This person need not be robotic per-se, but they have trouble with any truly creative endeavors. Research, art, poetry, and such are beyond them. Furthermore, they absolutely cannot get innuendo (e.g. creative interpretations).

- The soul connects mind and body. This one is a little weird - the modifiers to RP are sort of physical ticks rather than mental changes. This person has to control every muscle individually when they move, rather than just naturally moving by instinct. So when they move they are concentrating very hard and can easily be distracted. Every thing they do would be painstaking, and would use as few muscles as possible at any given time.

- The soul is hope. A bit of a darker one - the soul acts as protection against every bad thing in the world, because everyone at a deep level has an instinctual understanding that no matter what happens they can eventually live on and escape it in the afterlife. For this character, they are living in an endlessly decaying body - every minor cosmetic change is just a reminder of the inevitable destruction of their self and all that makes them up.

- The soul as social reality. Another kind of weird one. If you've ever read Neverwhere, that's a good inspiration for this. Basically, people only remember you if you have a soul. Otherwise, things you do tend to fade from memory and importance. The character is used to being ignored, used to being immune to the consequences of social misbehavior (at least the long term ones), and may be somewhat jaded and self-centered because of it.