Dealing Damage to Creature soulbonded to Deadeye Navigator
Is there I way that I could have destroyed either the Deadeye
  Navigator or the Nevermaker?


Yes.

Start out the same way, sending 4 damage to the Nevermaker. Your opponent activates its flicker ability. You let the flicker ability resolve, and the Nevermaker leaves and then enters the battlefield again.

This causes 2 triggers to be put on the stack, one is the Nevermaker's "leaves the battlefield" ability, the other is the "soulbond" ability on Deadeye Navigator (since your opponent controls both, he/she can arrange their order on the stack as desired). While both are on the stack, you can respond by activating Goblin Bombardment as you wish. Since neither Navigator or Nevermaker are soulbonded, they do not have the "flicker" ability anymore.