You don't have to orbit, you can just use a rocket to stay put. All observers that can communicate with infinity for all time agree about the infalling object. It gets frozen and redshifted at the horizon.
EDIT: in response to question
The issue of two objects falling in one after the other is adressed in this question: How does this thought experiment not rule out black holes? . The answers there are all wrong, except mine (this is not an arrogant statement, but a statement of an unfortunate fact).
When you are near a black hole, in order to stay in place, you need to accelerate away from the black hole. If you don't, you fall in. Whenever you accelerate, even in empty Minkowksi space, you see an acceleration event horizon behind you in the direction opposite your acceleration vector. This horizon is a big black wall that follows you around, and you can attribute the various effects you see in the accelerating frame, like the uniform gravitational field and the Unruh radiation, to this black-wall horizon that follows you around.
When you are very near a black hole, staying put, your acceleration horizon coincides with the event horizon, and there is no way to tell them apart locally. This is the equivalence principle, in the form that it takes in the region by the horizon where there is no significant curvature.
The near-horizon Rindler form of the metric allows you to translate any experiment you can do in the frame near a black hole to a flat space with an accelerating observer. So if you measure the local Hawking temperature, it coincides with the Unruh temperature. If you see an object fall and get redshifted, you would see the same thing in empty space, when accelerating.
The point is that the acceleration you need to avoid falling in is only determined globally, from the condition that you stay in communication with infinity. If you stop accelerating so that you see the particle cross the horizon, the moment you see the particle past the horizon, you've crossed yourself.
Modelling the formation of a realistic black hole can only be done numerically as the process is far too complicated for an analytic solution to exist. However there is a simplified metric for a collapsing non-rotating star called the Oppenheimer-Snyder metric and this captures the basic principles even though it is too simple to be physically realistic.
In the the Oppenheimer-Snyder metric the event horizon appears first at the centre of the star and then grows outwards until it passes the surface, at which point the collapsing star in entirely inside the horizon. The star then completes its collapse into a singularity, and this happens in finite proper time. So if you were on the surface of the star you'd meet your end at the singularity in finite time as recorded by your wrist watch.
It is true that for an external observer the event horizon never forms because it takes an infinite time as measured by the external observer's clock, and so the singularity never forms either. But to use this to claim the singularity never forms is to treat the external observer's time as somehow specially privileged and this goes against the spirit of GR. We should regard all observers are equal, and since the singularity does form in a finite time for the observer falling inwards with the star, it seems reasonable to claim the singularity does form.
It is true that in a universe of a finite age no observer will ever observe an event horizon, or indeed any singularity naked or otherwise, so in this sense we can "stop worrying". What worries physicists is whether the prediction of naked singularities implies some fundamental problem in general relativity. A naked singularity would imply a breakdown of causality and this it seems worrying that a theory which does such a good job of matching experimental observations could predict something that seems at odds with our expectations, even if we could never do an experiment to observe it.
Whether you could form a naked singularity in a finite coordinate time is an interesting question and I don't know the answer. In principle you could start with a rotating black hole, or more precisely an object that is almost but not quite a black hole, and fling mass in to speed up the rotation until it became extremal. However I don't know whether this could be done in a finite time as measured by the external observer.
Best Answer
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 ;)
Edit:
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.