Inspired by question I would like to ask what microcontrollers with CPLD or FPGA-like functions build in are available? The most interesting would be low-cost ones in friendly packages (non-BGA). The CPLD/FPGA portion should be big enough to allow implementing fairly complicated state machine (10+ states), fairly big logic function (10+ inputs), fairly big counters and shift registers (8+ bits) and be able to run at tens of MHz frequencies. Preferable method of design input for programmable logic function should be HDL based (Verilog or VHDL).
So far I have found two examples:
1) FPSLIC from Atmel
2) PSOC3 and PSOC5 from Cypress (those are not available yet, except in samples volume)