Rather than trying to distinguish whether or not your robot is moving + wheels moving or not moving + wheels moving, I suggest you simply scan the area with a proximity (distance) sensor. have your robot set up such that when the distance reading on the proximity sensor reads a value lower than your set threshold (ie what you have calculated to be 10 cm lets say), your robot turns to the right. When the distance reading from the sensor is greater than the threshold, have it move forward.
When it comes to available proximity sensors, I suggest either using an infrared (IR) rangefinder, or an ultrasonic rangefinder.
I would suggest using an ultrasonic rangefinder because is has a larger beam width than an IR rangefinder would have.
Reffer to this
for more info on IR rangefinders, and this
for ultrasonic rangefinders.
If placed properly, an ultrasonic rangefinder, because of its wide beam angle, may be able to monitor the entire front end of your robot, while an IR rangefinder will only be capable of measuring distance from a single point on your robot...unless you 'scan' the area with the IR rangefinder by mounting it on a servo. But thats another story
You can buy IR rangefinders from polulu. I suggest this
(4-30 cm range) or this
And you can get a really cheap ultrasonic rangefinder here
Edit: With the proximity sensor approach, an accelerometer will not be needed.
A side note: Trying to detect the hitting of a wall with only an accelerometer would be rather difficult. If your robot decides to suddenly turn, that may cause enough jerking to put the same amount of force on the accelerometer as hitting a wall would, which in that case will trick your robot into thinking it hit a wall. The worst part is, for accelerometer based navigation your robot actually has to Hit stuff, which is never a good thing...ok well sometimes it is
, but in this case it isnt. The proximity sensor approach allows your robot to navigate without hitting things.
However, obstacles such as chair legs and coffee table legs etc. may be missed by an ultrasonic rangefinder because they are so thin they aren't detected. This is where your accelerometer can play its part.