Cat5 no prob. Our whole system in London is on it.
You can get exchange emulators to allow the phones to share the line. We use one for our talkback. Any line to any outlet or calling between the outlets is possible. There's a 4 o/p one which is ok price-wise but wouldn't have enough o/p for you.
The ones I use are Panasonic, called Advanced Hybrid Unit KX-TA624. Cost a bit. If you were prepared to go lower number of ports then there's a 6 outlet one, have a look at
http://www.panasonic.co.uk/analogue-systems/kxt206e/index.htm