Motion is relative; you can always view this using coordinates in which the hole is at rest, and other objects are simply moving in the static field of the hole.
The hole's mass is unchanged, so from far away it behaves like any other object with the same mass.
A black hole is not "frozen in time". Again, the "time" of a distant observer is not a good standard of time when dealing with black holes. Someone who falls into a black hole would see time in their vicinity flowing perfectly normally.
Peter, Thank you for the amazing discussion!
If it turns out that the Universe has a finite lifespan and goes through some sort of a phase transition in the future or ends in some other fashion, what would then happen to our black holes and the observer falling into them?
No. The condition "nothing can move faster than light" is a local condition; no object can move faster than a light ray that is spatially co-located with it. But in curved spacetime, such as a black hole, there is no way to compare velocities of spatially separated objects--more precisely, such comparisons, while they can be done (by just comparing rates of change of coordinates), have no physical meaning. So while an object that falls into the hole could be moving "faster than light" in a coordinate sense, compared to an object far outside the hole, that comparison has no physical meaning; locally, the object inside the hole is moving slower than light rays in its immediate vicinity, and that is the only comparison that has physical meaning.