None of us were born knowing how to build a robot, or anything else, for that matter.
I have no experience whatsoever with electronics. Is there an easy to understand guide or book that could help me with that?
There is no ONE
guide/tutorial that would cover everything from A to Z and be easy for beginner to understand. Robotics incorporate many different disciplines and sub-disciplines. As with most of things You want to learn, picking fragments and gluing them together is the key. $50 Robot is a very good start, as it helps You to understand bare basics required to even think about building any type of more complex robot.
I have never had any programming experience.
$50 Robot does not cover programming aspect very well, as it only demonstrates how to flash microcontroller with pre-built code. To compensate for that You can always go extra mile Yourself, buy few LEDs, pots and resistors and follow tutorial links in following thread --> http://www.societyofrobots.com/robotforum/index.php?topic=14947.msg109175#msg109175
I read that if you haven't programmed before to try Lego Mindstorms. I can't afford those for now, so is there a cheaper alternative?
Are there any good all in one kits that actually teach you about robotics?
There are many different kits available, just use Google to look for those that meet Your budget. I must add that, in my opinion, kits are not very useful for learning robotics, unless You are interested in quick algorithm prototyping and don't want to mess about with hardware. Kits don't teach you how to solder, how and why to pick certain components and how to write low level software to command hardware at hand. If one can assemble and program a kit it is not necessary true that one is able to build robot using low level components, however if one is capable to build robot from scratch it is very likely that building a kit wouldn't be much of challenge. Also, kits normally come with their own development environment which is not suitable for any other microcontroller out there, where learning to program plain
microcontroller allows You more choice next time You design a robot.