Does anyone know if it's possible to sort by two attributes, eg. Alphabetical and Out of Stock

Not possible. You should be able to set up stock status as a facet though?

I have managed to do that but colleague wanted to see if we could push the out of stock items to the bottom of the page

Nope, sorry