What are some smallest, cheapest microcontrollers with USB built in?
The best way to find those microcontrollers would be at a site such as digikey. Here is the list of all their microcontrollers. 

Use the filters to pick Atmel as a manufacturer. 

Then filter to leave their AVR family on the list. 

And finally, filter by connectivity. Choose all items on the list that have "USB" or "USB OTG". Hold down CTRL to pick multiple items on the list.

Off the top of my head, one of the simplest would be ATmega88U2. The U2 tells you it's a regular ATmega88 with a USB controller built-in.