Any percentage of lightspeed is fine, as long as it is above 1% lightspeed.
Pfft. Unless you can get a Lorentz factor of at least two, it doesn't deserve to be called a relativistic kill weapon.
The bullet should not have any rockets, and only a starting spark or propellant is allowed.
Happily, relativistic rockets are harder to make than relativistic guns, because physics hates you and your toys, as Tsiolkovsky has observed.
I'm going to blatantly abuse the wiggle room allowed by "starting spark" and break out Jordin Kare's sailbeam interstellar propulsion system. As many have observed, going fast enough for interstellar travel, even a puny 0.1c, is really hard, and using rockets is basically a terrible idea if you want to go faster.
The sailbeam is a laser-driven light sail system, that uses a powerful laser (the "spark") to drive a stream of small sails made of suitable dielectric materials (the "propellant") to considerable speeds. The performance limits of such a thing are mindboggling... Kare suggests that maximum acceleration of a sail could be 32 million gravities (or zero to lightspeed in .97 seconds) though practical implementations probably aren't going to hit those sorts of levels.
The whole idea of the sailbeam was that each sail can be efficiently ionised and then deflected by a magnetic shield to transfer momentum, which is obviously not what you want. Instead of using the stream of relativistic lightsails directly, you bounce them off a magnetic shield behind the actual kill vehicle to drive that up to relativistic velocities. That can be a lot heavier and denser (making it impractical to deflect with mere human-generated magnetic fields) and might also have other useful adaptations like having a bursting charge to turn into a cloud of debris that is impractical to intercept. Lots of possibilities.
Sure, it doesn't look much like a "gun", but that's a good thing because guns of the conventional kind cannot possibly do what you want... too big, too hot, to inefficient. Nonetheless, it clearly ain't a rocket.
(and to those who might ask "why not just use the laser?" this could hit a target at arbitrary ranges, whereas all lasers will be diffraction limited and have finite ranges, or have planet- or star-sized optical elements)
Do note the size of this system... you probably want at least a light-second's worth of space for the sail "runway", which is about 300000km, plus sufficient distance for your kill-vehicle to get up to speed. The latter is likely to be much longer, as accelerations will be quite a few orders of magnitude lower. That gives "barrel" length of a few tens of millions of kilometres (light minutes) depending on how fast you want your projectile to go. That's why you don't want a physical barrel on this sort of weapon!