How should I connect ground wires for new ceiling fan?
If I understand correctly, based on your recent update, you have access to all of the ground wires.  As you said, they were not attached to anything and you were able to pull them back into the box.
You should pigtail the fan into the current grounding path.  This can be accomplished by taking a short piece of bare copper (of same gauge as current ground wires) and tie it together with the other grounds using a wire nut.
Should your fan be grounded?  Yes, ground it.  There is a bigger problem here though.  If the grounding wires in your current cables are not connected, then you do not have ground downstream.
As EdBeal pointed out in the comments, this box is not rated for a ceiling fan and cannot provide the support that a fan requires.  It should be replaced as well.