A very small microcontroller that can be programmed wirelessly
That is going to be very difficult.  

The typical way to do this is to have two MCU's.  One with a wireless connection that can program the other MCU's.  The programming MCU would require some firmware in it that can receive the wireless communications and twiddle the pins on the main MCU to program it.  You also have to power this circuit, which will put a burden on your toy's batteries.

This is a big project to make one MCU program the other, and the number of people who would benefit from this (a.k.a. pay money for it) is small.  That's why you don't see this in the market.  While cool, the market for it isn't large enough to justify the development costs.

If I were you, I would instead focus on a way to make the programming signals accessible without removing the PCB from the toy.  There are many ways to do this using fancy connectors or even just spring loaded "contacts" that touch metal bits on the toy.  

Sometimes the straightforward approach is the best.  Skip the wireless.