I'll try to answer your questions one-by-one, though I'm afraid that they are so basic that these answers alone won't be able to help you very much in the long run:
1/ No, one can run AMR on any starting mesh. It doesn't have to be a square. A few examples of adaptive meshes on other domains are here: https://github.com/dealii/dealii/wiki/Gallery
2/ Cell-centered and vertex-centered schemes are, in some sense, dual to each other. You can often think of one in terms of the other defined on a shifted mesh. I imagine both of them to be equally easy/difficult to implement.
3/ As long as you are on the unit square, you can compute the locations of vertices of a cell if you know how you arrived at that cell by mesh refinement. On the other hand, if you start with any other mesh, you will have to store the locations of vertices.
4/ There are other approaches to doing AMR than using quadtrees. For example, you could do longest-edge bisection or red-green refinement for triangles. (Since you already found my video lectures, this would be lecture 15.) Quadtrees are a particularly useful approach for quadrilaterals, though.