Should inputs be shuffled for training a model with expected time dependency? Consider a prediction model with numerical inputs and outputs.

Suppose data is inserted tick by tick, i.e., when new data is available it is inserted asynchronously. Current output depends on current inputs and past inputs and outputs.

Normally for training, inputs/outputs pairs are shuffled since no time dependency exists. 

With such time dependency, should inputs still be shuffled?
You don't shuffle the actual inputs and outputs in your prediction model. Nevertheless, depending on your prediction model you might have to model the sample distribution including mean and variance. To model sample statistics you can use methods like bootstraping. However, this method assumes your model and inputs to be stationary (none changing distribution over time) and therefore neglects timely-variations, like structural breaks. But there have been modifications, e.g. bloc bootstrapping, to overcome this. You can read more about sampling in time-series here