There are a few tip-offs that Verbal is Keyser Soze:
When they are released from the lineup and go out on the street, while Keaton is talking to Edie Finneran, the camera cuts to each of the others. In one shot Verbal is holding/smoking his cigarette between thumb and forefinger and palm facing up. This is an Eastern European trait commonly picked up by others in the region like, say, Turkey.
Before Kujan arrives, Verbal is shown glancing around the office, noticing details that he can turn into his impromptu story.
Before Verbal talks about Kobayashi, there's a shot of Verbal looking up at Kujan just as Kujan is taking a drink from his coffee mug, giving Verbal a clear view of the "Kobayashi" insignia on the bottom of the mug.
Verbal mentions (not an exact quote) that part of what makes Keyser so dangerous is having the will to do what the other guy can't, then just a few scenes later we see him shoot the guy in the car that Keaton keeps threatening but never actually pulls the trigger.
Verbal starts to recount incidents where he wasn't there. His arrest is the the only one not shown despite the fact that it is Verbal who is telling the story. The reason is of course because he is Soze and wasn't arrested.
Verbal smiles slightly when convincing Kujan that Keaton is in fact dead, stating that he knows it for a fact.
Peter Greene, the actor who played Redfoot was uncredited because the character never existed.
The way things go down in the "jewel" heist is another point in favor of Verbal being Soze. First off, assuming that we can believe our resident Unreliable Narrator, Soze & Kobayshi set the robbery up in the first place so that when it went bad and Saul died, it would make the Suspects come to them and Saul's death would be blackmail material to use against the Suspects. That doesn't happen without the death of Saul Berg though. So when it looks like Keaton won't go through with his threats and kill Saul, who finally steps up to do it? Verbal. Why? Because he needs that death to lure the Suspects into a bigger trap.
It's easier to realize that Verbal is lying when he starts to recount incidents where he wasn't there.