There are several differential agars that claim morphological (color pattern) differentiation (I have not used them, so I don't know how robust the reactions are with many strains of the same type of organism).
It can be diagnosed in the lab due to characteristic swarming motility, and inability to metabolize lactose (on a MacConkey agar plate, for example). Also P. mirabilis produces a very distinct fishy odour.
in my experience on HE agar usually, but not always, Proteus has a small transparent "halo" around the black of the colony which is a bit more "fatty" but the colony is generally smaller. Also, if you are brave, you could try to "smell the difference". On SS agar, Proteus, to me, usually smells like "rotten cooked fish" instead Salmonella smells more like "roasted chestnuts". But again, is not a reliable rule.
You could always isolate the colony on normal blood agar (COS) to see the Proteus typical swarming.
Other thing I do, often, is a slide with gram. Salmonella, usually, look bigger and a lil'bit more rectangular, also if you "play with the focus" of the microscope, you could see a "larger edge" around the Salmonella cells.
urea test is good, or you can use the BBL phenylalanine agar slant (see http://www.bd.com/ds/technicalCenter/inserts/L007487%2807%29%28201101%29.pdf ). The genera Proteus, Morganella and Providencia are the only ones that are positive to this test.