There are several ways you can do this.
I'd start off by seeing if any of the cell-phone charger wall-warts are sufficiently small. These normally supply about 5V at current ranging from 100 mA to 2 Amps. The Apple cube adapters are nice and small (about 2.5cm cube).
If that's too large, you can purchase replacement wall receptacles that have a built-in 5V USB power supply. You could assemble the LEDs & current-limit resistors right onto a cut-down USB plug.
You can also do a capacitive-type power supply. However, I'm reluctant to steer you in this direction if you aren't aware of the hazards involved and know how to choose the appropriate components. This is one situation where choosing the correct capacitor and resistors means the difference between a safe circuit and a fire hazard.