Hi
As explained above most of the basic should be covered by any online booking system, there seem to be a few out there ranging from the expensive where they want you to buy their laptop/PC etc to those who allow you to sign up and pay as you go so you feel safe that you can cut your costs at anytime, (a lot to be said about that in this day and age) sign up for a free trial and if they don't offer one then that will tell you enough.
You can do also most eveything these days online; shopping, book holidays, banking, the list is endless so why not book a hair or beauty appointment? Yes desposits may be a good thing for new clients but regulars you may have differnt feelings about and I'm sure 95% of any established business is made up of regulars, so "hopefully" the trust element is there, if not you would be able to block the client from the site or make them pay a deposit.
One thing to remember with an online booking system, YOU should still be the one in overall control.