You could have a look at RatSLAM, as it would fit your constraints very well (works indoor + outdoor, uses a camera as input). There is an open source version of it available, too: OpenRatSLAM.

Try using Wifi data to localize. Probably you can train the robot with wifi data patterns with respect to the position the robot is in. 

With the image inputs you can use SIFT, SURF algorithms which can help to match same structures in the images. 

Thank you Samya. WiFi could be a good idea.

Other suggestions are still welcome, as this is a work in progress!

In the past, I advised some students using SLAM for multi-robot systems. We used ultrasonic sensors for measuring distances all around the robot while it continues running (like a radar). In our case, robots were located into a maze such that corners serve as fixed points. SLAM ran very well and the robot could locate itself into a virtual map of the maze. 

You can try with a camera in the same way we used our handmade radar, locating corners or suitable fixed objects in order to give fixed points for the SLAM method.

There is not one best way to solve this - it really depends a lot on the specific requirements and the sensors that you have at hand. In general, you will need some estimate of the robots own motion (either the steering commands, dead reckoning, or optical flow), and observations of the robots environment (camera, laser, Wifi, magnetic field, etc.). These measurements you can then combine in a fusion algorithm (Kalman or particle filters, GraphSLAM, etc.) to generate a map of the environment (either landmark- or grid-based) and then localize the robot within the map. With cameras and laser scans, you may achieve very high accuracy and robustness, plus there are some good open-source implementations available online (have a look at http://www.openslam.org/). Wifi and other signal sources are "cheaper" in some ways - no video recording and analysis necessary, etc., but then again, accuracy and robustness may be lower. If you just want to experiment and get familiar with SLAM, I'd suggest to use a camera-based approach and one of the publicly available implementations.

Totally agree with Hardegger's answer.   I might add that my students have had good luck with some of the ROS supported tools like hector slam (http://wiki.ros.org/hector_slam).  However, ROS (http://www.ros.org/) has a bit of a learning curve and might not be appropriate for your project. 

You could have a look at RatSLAM, as it would fit your constraints very well (works indoor + outdoor, uses a camera as input). There is an open source version of it available, too: OpenRatSLAM.

From my previous experiences with the Wi-Fi signal strength, I strongly oppose using Wi-Fi for this purpose. RSS is too dynamic and unpredictable to be used for this purpose. Many environmental parameters may affect it and it is not a reliable choice.

As for the a good solution to tackle the problem with, even GPS is not accurate (better say precise) enough to be used for this purpose. Here, the low accuracy of the sensory system is making it a difficult problem area. Sensor fusion can only improve quality (even sometimes accuracy) of the measurements and cannot increase precision of the measurements as it is required here. In finding a solution, everything depends on the desired positioning accuracy you aimed on, at the end of your track (and for a track with what length?).