You can avoid the fee by cutting your trainer instead of replacing him. You do this after the training goes through and before the salary is payed. Then after the salary goes through you get the replacement. Best time to do it is when you are doing team training, so that you can keep that lvl 1 trainer an extra week or two and save some more.