Ideally, one would always do ritual handwashing (netilas yadayim) and say Asher Yotzar after going to the bathroom. (Source: Shulchan Aruch OC 4:18 for handwashing; here for asher yatzar) However, in practice this can sometimes be hard to do--especially in public restrooms, and/or without a washing cup. Is it better in these cases to skip the blessing altogether, or to say it with (ritually) unwashed hands?
Yalqut Yosef - Qizur Shulhan 'Arukh (Orah Hayim 3:2) states (my translation):
צריך ליטול ידיו כדי לברך אשר יצר... [אבל] מעיקר הדין מותר לומר דברים שבקדושה אחר ניקוי ידיו במידי דמנקי
One should wash one's hands in order to recite "Asher Yazar"... But, strictly according to the letter of the law, one is permitted to say devarim shebiqdushah after cleaning one's hands with midi dimnaqe'i (i.e. items that clean).
Therefore, later (Orah Hayim 6:14) he states (translation):
בשעת הדחק [יכול] לנקות ידיו במידי דמנקי כדי לברך אשר יצר
In a pinch, one may clean one's hands with midi dimnaqe'i (i.e. items that clean) in order to recite "Asher Yazar".
In short, ascertain that your hands are clean of visible dirt, rub them gently along the wall (if running water is unavailable), and recite "Asher Yazar".
If there is no other faucet available, then let him wash in the lavatory, exit, dry his hands, and bless asher yatzar. He should not skip it.
If even he has no water at all, let him rub his hands on something and bless.