An object falling into a black hole freezes from the point of view of a remote observer. This only means that it stops moving with respect to the black hole. In other words, the black hole and the object will start moving together. There is nothing that prevents the singularity from moving, and there is nothing that prevents the object from moving. The only requirement is that they move together.
Additionally, having a moving black hole is very simple. You just need to move with respect to the black hole. Motion is relative ;)
You ask how is it possible for an object frozen in time to move in space. Nothing prevents something with 'frozen time' to move in space. Indeed, if you think about it, everything that goes at the speed of light has its time frozen. Going faster in space means that you go slower in time, so the object near a fast moving black hole would experience an even slower time. You would see such object crawling even slower towards the event horizon, compared to the case of immobile black hole.
And it would make no difference if the object is in the front or in the back of the black hole, apart from the fact that, since the object is getting closer to the event horizon, if it is on the back, it will move slightly faster than the black hole, and if it is on the front, it will move slightly slower. But the rate at which it gets closer to the event horizon would be the same.