At what velocities would the (aerodynamically shaped) projectile just burn up?
Only a few km/s. Read up on the Sprint missile, which could reach Mach 10 in 5 seconds (which would be about 3.5km/s, though that slightly depends on the altitude it had reached at that point) which resulted in skin temperatures of 3400 degrees C and needed an ablative heat shield. The Sprint also went up pretty quickly to try and get out of the densest part of the atmosphere ASAP... shooting horizontally at sea level, you'd have much greater heating to deal with.
In any case, range at low altitude and high speeds is clearly limited by the lifetime of your ablative heat shield. On the bright side, it'll look awesome as it'll form a plasma trail. Hope you weren't intending to be at all stealthy!
If somehow the burn-up-problem would be solved (handwaved), what would be the next threshold? Is there a velocity that would just make matter disintegrate?
When the stagnation pressure behind your bow shock exceeds the yield strength of your projectile. Or to put it another way: the force of the air ramming into the front of your projectile is greater than the strength of the bonds holding your material together, and it will simply break up like a jet of fluid, starting at the tip. It'll be eroded away all down its length til nothing is left but an expanding cloud of fragments, which will probably resemble an explosion.
Due to the lack of studies on hypervelocity projectile weapons (along with the lack of such weapons), I'll turn to papers on shaped charges. The impact pressure of a shaped charge jet with a solid object exceeds the yield strengths of any material, so both can be treated as incompressible fluids splashing against each other. Obviously there are differences between a soft shaped-charge jet penetrating solid armour, and a hard projectile penetrating air (for a start, air is definitely not an incompressible fluid), but the basic idea is the same so this figure probably isn't too wrong. Take the figures with a small pinch of salt, but they're a good first guess.
Looking at studies of shaped-charge jets, you get handy formulas like $$P = L\sqrt{\frac{\rho_j}{\rho_t}}$$ where $P$ is the penetration depth, $\rho_j$ and $\rho_t$ are the densities of the jet and target respectively and $L$ is the length of your projectile. In this case, the "target" is the atmosphere itself. A half-metre long tungsten rod will therefore travel $0.5\sqrt{19300 / 1.225}$ or $62m$ max through the air once it had exceeded this critical velocity, disintegrating as it went, regardless of its temperature.
What would be that velocity threshold, you ask? Well, uh, I haven't the faintest idea (aside from "higher than re-entry speeds"). Compressible aerodynamics turns out to be Quite Hard, and my previous efforts to wrestle with it came to nothing. But now you know the magic words to search for, so maybe you'll have more luck than me.
If I had to hazard a guess though, I'd look at shaped charges again. The tip of shaped charge jet travels at about 10km/s. Armour is about 10000 times more dense than air. The force exerted by a fluid jet is $F \propto {\rho}v^2$, so you'll need your projectile to travel about $10km/s * \sqrt{10000} = 1000km/s$ to develop the same forces from impacting air. This is a very, very loose approximation and shouldn't be taken too seriously. It does seem plausible though, give or take an order of magnitude.
I was thinking about having it fly at around 75000 km/s (~0.25c)
This is more than 10 times faster than the 1000km/s threshold I invented above, so I'm pretty certain that there's no way that a projectile travelling this fast could stay intact even if you did handwave all the heating issues away.
Definition of viable for this question: "Emerge" already at full velocity within earth's atmosphere, travel for 100-10000 m in a straight line, hit a target while still being a solid lump of matter.
Well, if your projectile was long enough, some of it might survive to hit the target. You'd need to fire it perfectly straight though... any deflection or manufacturing defects will cause bits of it other than the very tip to be blasted off, and that will a) ruin your accuracy and b) ruin your range. You're clearly limited in how long you can realistically make your projectile, and given the speeds you want it'll almost certainly have to be too long.
Short answer: nope.