Have you played the classic boardgame Scotland Yard/Mr. X.
A mobile game version is in development by the University of Bonn.
For more info (mostly in German) check out: http://qeevee.com/projects/misterx
The game sounds promising, hope I can test it soon.
Update: I had the possibility in several settings with teenagers and it worked very well. For me the best „spontaneous“ game yet. And it works with Android and on the iPhone.