a few questions about your list of requirements...
do you mean USB host post or just the ability to read data off the device via USB?
do you mean you want to be able to program the device from the Linux environment or do you actually want the device to run Linux?
if you are looking for a device that has a USB host port an runs Linux then you probably need to adjust your search terms.
try searching for "embedded Linux processor" rather than "microcontroller".
a broad generalisation here:
most microcontrollers will not have sufficient resources to run a full OS like Linux. (although there are minimal RTOS available for microcontrollers.)
as a result most microcontrollers cannot have USB host ports as you need to run a full OS to manage the USB bus and run USB drivers, etc.
there are devices on the market that have an embedded processor on the same board as buffers to handle TTL I/O but they are rare.
a more common approach is to have an embedded processor to run your OS connected to a microcontroller to handle I/O.
there are a few of us on this forum taking this approach in one form or another. my interpretation documented here: http://mrdunk.googlepages.com/processor