Almost universal string hashing in $Z_{2^n}$ and sublinear space
Yes. Wegman and Carter's "New hash functions and their use in authentication and set equality" (mirror) shows a scheme meeting the requirements stated (almost universal, over $\mathbb{Z}_{2^b}$, sublinear space and randomness, linear evaluation time) based on a small number of hash functions drawn from a strongly universal family.

This is sometimes called "tree hashing", and it is used in "Badger - A Fast and Provably Secure MAC" by Boesgaard et al.