Personally; unless you are required to have cabling that will last more than 7 years or so, I'd go Cat5e.
As others have mentioned, Cat6 is basically better quality and will hopefully support future enhancements better than Cat5e. However, at this point in time, there is no practical difference; both support 1000Base-T (Gigabit) up to 100M max (using all four pairs remember).
Yes, you should definitely use PoE. Remember, not using PoE can also be costly - you'll need lots more power sockets at desks. More importantly, how would you provide battery backup in times of power failure for all those sockets? (people still expect phones to work during power failures and this is probably more critical in a school.) Much easier to put a UPS in the wiring closet...
If you have recent edge switches then add mid-span power units to them. Otherwise, buy new PoE switches that support the 802.3af standard. Check that your IP handsets will be compatible. Check the power budget on each switch as some handsets consume more power than others and most switches do not have PSUs capable of handling the highest power devices on all ports.
Finally - if you're looking at Avaya, make sure you have a Customer Infrastructure Readiness Survey (CIRS) performed.