"seems it would be preferable to become a consequentialist – indeed, iti s be virtually impossible not to be a consequentialist."
A consequentialist about what? No one can be a consequentialist about their own actions, because no one has perfect knowledge of the ultimate outcomes of their actions..practical morality cannot be consequentialism.
Expected utility doesn't have to be deterministic.
This was demonstrated, in a certain limited way, in Peterson (2009). See also Lowry & Peterson (2011).
The Peterson result provides an "asymmetry argument" in favor of consequentialism:
Another argument in favor of consequentialism has to do with the causes of different types of moral judgments: see Are Deontological Moral Judgments Rationalizations?
Update: see Carl's criticism.