What sensors should I use to get a feel for direction and speed/distance

I've been working on my latest robot: https://www.robotshop.com/letsmakerobots/node/39087 which uses the PING))) and a compass sensor. I thought it would be enough to get an idea of the heading and distance to I could keep track of the path travelled. 

Boy I was wrong. First of all the compass doesn't work properly indoors so the readings are far from usable to get an accurate reading for the absolute or even relative heading. 

The ping sensor also does not work properly for the distance as I am approaching in a wrong angle, the signal is lost and the readings are off. 

I then tried by calculating the speed of the motors and tweaks my calculations through observations but the speed does not seem to be accurate and is changing way to much to be good. 
I calculated the ms required per cm with a big enough decimal fraction. Did the same for the angles when turning (ms per degree) but I notice that a motion that takes 800ms doesn't do the same thing. There is quite a big error margin which renders this method useless.

I also tried using a photocell aimed at the wheels and used some white paint to mark the wheel at certain degrees however as there is only a contrast change, the readings from the photocell between the white and black parts is noticable but to little. If the ambiant light changes while driving (moving through shadow) the readings are off. 

I am determined to continue my pursuit to map and localize the path taken by my robot but I think I have to adjust my sensor strategy.

Anybody got some tips which sensors I need to use so I get a proper and rather accurate feel for direction and speed?

First of all I was thinking on using a Hall Effect sensor to capture the speed of the wheels. However, I am using continous servo's and the RPM is around 1 so I don't know if I can get an accurate reading with the hall sensor.
Maybe I need to switch the motors and use a proper encoder on the shaft or use the hall sensor to measure the gears. I rather use the components I have and I only have continous servo's so if there is a sensor that could help me on this, that would be great.

If I can get an accurate reading of the motion of the wheels I can also measure the heading change and distance travelled which is basically all I need.  

Would an IMU help? I never used these and they also are quite expensive. However if they can help me and work well indoors (unlike the compass module) than I might think about adding them. 

If you are using continuous

If you are using continuous rotation servos, you can measure traveled distance by counting servo pulses and note how much the robot travels when issued 10 pulses and divide that distance by 10 to get the distance per pulse. But you have to generate the pulses manually and not rely on the Servo library. Kind of like you would use a stepper. This is not an accurate method, the best is with encoders, even for steppers (they might skip a step). And with single channel encoders, if you count both changes (from low to high and from high to low) you might get in a situation where the wheel is vibrating at the changing point and several counts are registered. Quadrature encoders generally avoid this problem that single channel encoders have.

To avoid ultrasonic sensor problems use an infra red sensor in parallel and compare measurements. IR sensors have their problems too when trying to measure distance to a soft material that does not reflect IR. So, if both sensors indicate empty path, trust them, if only one indicates that, trust the one that says obstacle detected. And don’t forget to read several times, discard the anomalies and average the rest.