Here's an example of Charles Babbage's difference engine (invented in the early 1800's), reconstructed with legos, which can be seen operating in a video below. The difference engine can calculate polynomial functions with sufficient accuracy to approximate non-polynomial functions like logarithm or square root. These could then be used in a table to look up the approximate results of the function for a certain input. Considering that slide rules were in common use as recently as the 70's, the difference engine was really ahead of its time.
Perhaps best of all, mechanical computers make mechanical noise - perfect for providing that steampunk atmosphere!
P.S. That picture is from The Guild. The episode and show are definitely worth watching :-D