There is no time restriction on re-spending transaction inputs; the same transaction can immediately be double-spent - resent with less change and more fees. The unconfirmed transaction will be discarded from memory pools when a replacement transaction using the same inputs is included in a block.
I think you misunderstood any node following the reference client rules will drop and refuse to relay a double spend. So if you have tx A and you wish to replace it with tx B, when your node broadcasts tx B to the 8 (or 50) immediate peers the most likely outcome is they all detect tx B is a double spend of tx A (because tx A is in their memory pool) and promptly drop it. You can keep broadcasting tx B thousands or even millions of times and they will happily drop it each time.
Now eventually nodes do "forget" about unconfirmed tx so after that you can broadcast tx B, and your peers not having a record of tx A relay the tx on to other nodes, who will relay it to other nodes, and eventually every node and miner will know about tx B. There is one "gotcha" though. As long as your node knows about tx A (it is still in the wallet) your node will keep reminding other nodes about tx A (who will remind other nodes) this will ensure that nobody ever forgets about tx A preventing a spend of tx B.
So simple version:
a) Bypass the peer network and get the replacement tx in a block.
OP can contact a mining pool and ask him for help (likely for a fee)
or
b) Allow the network to "forget" about the original tx and try again.
OP (or someone who in the future is in the same scenario and doesn't want to need to contact a miner) can remove the tx from the wallet file, wait long enough that the network forgets about it and create a replacement tx.
