Is it possible/feasible to send out large amounts of small transactions without paying fees? How long would it take to process 1000 transactions from the same wallet, with outputs ranging from 100 bits to 1000 bits and no transaction fees for any of them?

How about if 1000 of these transactions were sent out every hour? Would Bitcoin be able to handle this?
Individual miners have different standards for what fees they will accept. Most simply aren't going to process a transaction without fees, so you'll be waiting for somebody to generously record your transaction to the blockchain without compensation. I've never tried this, but I've seen people say that they've had to wait days. It will vary, of course. If you get impatient you could always propagate another transaction that spends the same exact funds, but allowing some of them to be used as a fee.

I've heard estimates of how many transactions the blockchain can handle that range from 3 to 7 per second. I'm really not sure what the average transaction size is, but they all have to fit in a 1 megabyte block. Even a miner who generously records transactions without a fee is almost certainly going to give priority to transactions with a fee attached, so some of your transactions might get recorded and the rest left to wait for another generous miner to get a block. Unless the inputs of one transaction require the outputs of another, you won't even be able to know which ones will get recorded first.