So you have power TO the starter relay, but not OUT of the starter relay, and you have replaced the relay, correct?
In that case, something is not telling the starter relay to engage. That can be done with a switch that provides the ground, and the coil is always energized, or ground is always provided and a switch provides 12v. Find out which way it works (probably supplying 12v) and see if you get the right signal when you turn the switch.
If not, disconnect the factory wiring. Now supply what is needed (BOTH ground or power) with a jumper. That should tell you if that's the problem. Give it a known good ground, give it a known 12v. If it works, then you can reconnect ONE of the two coil terminals and disconnect the jumper. Now try again with the key. If that doesn't work, swap.
Should tell you which side isn't getting the job done.