are these outputs strong enough to open/close small relays without an additional power source?
Unfortunately no, there may be a version that does but the best thing would be to use a driver chip like the 2803.
This chip turns 4 arduino outputs into 16 outputs on the chip, by combining different high/low inputs on the chip (4X4 combo's=16), right?
Correct, but the equation is 2^4 = 16 (2 to the power of 4).
Rob