That's a good start, but point 2 can be made a bit more precise. Let's say the asteroid starts at $\mathrm{B}_0$ at time $0$ and has constant velocity $\dot{\mathrm{B}}$. Then its position at time $t$ is $$ \mathbf{B}(t) = \mathbf{B}_0 + t \dot{\mathbf{B}}. \tag{1} $$ Your $\mathbf{C}$ is just some point on this line, which we would know if only we knew $t_\mathrm{hit}$, the time at which the bullet hits the asteriod: $$ \mathbf{C} = \mathbf{B}(t_\mathrm{hit}). \tag{2} $$
But how to find $t_\mathrm{hit}$? Well, we can work form the perspective of the bullet, whose position I'll denote with $\mathbf{A}(t)$ (no need to worry about the ship, since it's not moving). As before, we have $$ \mathbf{A}(t) = \mathbf{A}_0 + t \dot{\mathbf{A}}, \tag{3} $$ except here $\dot{\mathbf{A}}$ is an unknown vector constant. Actually, it's not entirely unknown, since it must satisfy $$ v^2 = \dot{\mathbf{A}} \cdot \dot{\mathbf{A}} = \dot{A}_x^2 + \dot{A}_y^2 + \dot{A}_z^2, \tag{4} $$ where $v$ is the fixed bullet speed. Now again the impact point must occur along the bullet's trajectory, and after the same elapsed time: $$ \mathbf{C} = \mathbf{A}(t_\mathrm{hit}). \tag{5} $$
Equations (1), (2), (3), and (5) combine to form $$ \mathbf{B}_0 + t_\mathrm{hit} \dot{\mathbf{B}} = \mathbf{A}_0 + t_\mathrm{hit} \dot{\mathbf{A}}. \tag{6} $$ Then (4) and (6) form a system of 4 scalar equations in 4 unknowns ($t_\mathrm{hit}$, $\dot{A}_x$, $\dot{A}_y$, and $\dot{A}_z$) and so can be solved uniquely.
(Actually there might be two or zero solutions, depending on the actual values. Zero solutions means your bullet is too slow to ever catch up. Two solutions probably means one corresponds to negative $t_\mathrm{hit}$, as though the bullet went from the asteroid in the past to the ship in the present. Though it might also mean there are two chances to hit the asteroid.)
For a moving ship, your bullet's velocity in these coordinates, $\dot{\mathbf{A}}^\mathrm{bullet}$, is given by the sum of the known ship's velocity when the bullet is fired, say $\dot{\mathbf{A}}^\mathrm{ship}$, and the to-be-found velocity of the bullet with respect to the ship, $\dot{\mathbf{A}}^\mathrm{relative}$. To work with this, just solve for $\dot{\mathbf{A}}^\mathrm{bullet}$ (aka $\dot{\mathbf{A}}$) as above, and then calculate $$ \dot{\mathbf{A}}^\mathrm{relative} = \dot{\mathbf{A}}^\mathrm{bullet} - \dot{\mathbf{A}}^\mathrm{ship}. $$