"Starter Kit for electronics" - What to buy?
While there is no single kit to my limited knowledge, that meets all the needs described, here are some suggestions:


Get a basic beginner-level Electronic Design book (or two), even if it seems more basic than you would like. 


Electrical Engineering 101, Darren Ashby: You can get the second edition as an eBook, for as little as $1, but I prefer paper books personally. The third edition isn't essential at this stage. This isn't necessarily the ultimate such book, but it's handy.
Practical Electronics for Inventors, Paul Scherz: Again, just $1 in eBook form, up to $17 new from Amazon. Nice book, focuses on the inventor mind-set rather than just being an Electronic Engineering purist effort.






Decide on a beginner-friendly microcontroller platform for your initial forays... You can change your mind later without writing off prior purchases.


There will be recommendations for several platforms, such as the Parallax BASIC Stamp (yes, coding is in BASIC), the PICkit (PIC microcontrollers), the Texas Instruments MSP430 Launchpad or (preferably) Stellaris Launchpad, and perhaps the most popular and best-supported by its community, the Arduino family (Atmel AVR microcontrollers)
My personal and admittedly biased suggestion would be the Arduino family, for a few reasons: Way better community support for both accessory hardware ("shields") and code, availability of very capable clone boards in the $10-$20 range, sometimes better than the official Arduinos, and massive, massive pop-culture recognition which in itself ensures ongoing peer support.
This bias is backed by the ease with which many non-Electronics people get up and running on microcontrollers after being introduced to an Arduino. Yes, purists will argue that 'duino ain't real electronics, but whatever...






Pick up either a learner's kit, or one of the cheaper (clone) development boards with some add-ons. Here, I'll restrict my suggestions to the Arduino space, others can chime in for the other platforms.


InduinoX Learner's Kit, my personal favorite for both board construction quality and the thoughtfulness of the extras they added to the Arduino stock product. Also, the actual microcontroller is a socketed DIP, so if you blow one up, replacement is easy.

Alternatively, a Meduino Nano Enhanced - An inexpensive (under $12 shipped from eBay) fully functional Arduino Nano clone in a tiny form-factor which fits onto a mini-breadboard. It can be switched between 3.3 Volt and 5 Volt operation, a great advantage when experimenting with 3.3 Volt sensors and devices.

Finally, for a bigger budget, Sparkfun's Inventor's Kit for Arduino:

Again an excellent kit, albeit a bit pricey at nearly $95, the kit includes a bunch of different sensors, LEDs, resistors, buttons and other parts to get started. As the parts get used up (or blown up), SparkFun's Parts Refill Pack comes in handy:

The SparkFun ProtoSnap Pro Mini (under $30), a really neat idea wherein you snap off individual sensors / mini-boards and interconnect them as needed, to get an Arduino Pro Mini, a USB interface device, and a few other peripherals.
 






If you selected a developer board above, rather than a full kit, then there are some excellent sensor collections designed for Arduino and other embedded development platforms, that are worth considering:


My recommendation: The 37-in-1 Sensor Module Kit for under $56 shipped:

Alternatively, the much pricier SparkFun Sensor Kit (nearly $200), which has some advanced sensors:







Finally, get yourself at the very least, the following tools / components to get you started:


A digital multimeter - anything from the cheapest $5 multimeter from Harbor Freight Tools, to as expensive as you can afford.

A soldering iron - I don't have a specific recommendation, as I am still looking for the perfect iron that I can actually afford.
A bunch of mini solderless breadboards: A pack of 10 for under $12 shipped is a very worthwhile expense.

A regular-sized solderless breadboard, such as the MB102 boards sold for as little as $3 on eBay.

A breadboard power supply, 3.3 and 5 Volt simultaneous outputs from wall-wart, USB or 9 Volt battery, they are typically just over $2 shipped from eBay:

A set of assorted resistors, all standard values, from whichever vendor works out cheapest for your geography. I'm in India, this one works for me.
A set of capacitors like the resistors above if available, or at least a bunch of 0.1 uF ceramic type, and 1 and 10 uF electrolytic type capacitors, for decoupling and miscellaneous uses.





While it is impossible to make an exhaustive list of all you could possibly need, the above, or whatever subset of it makes sense to you and to your pocket, should serve as a starting point. 

For every one of the items above, it would be useful to search the web for alternatives, and for better price deals. Do not take these suggestions as the best for you, they simply worked out the best for me.

Further, no matter how comprehensive a kit you start with, pretty soon you will need something not thought of before, so be prepared to regularly scan eBay.com, DealExtreme and other such sites, with "free shipping" checked, for every new need.