The new transaction will have to change, because as said, it will be rejected. You can slightly change the locktime value to one lower, and it will produce an entirely different hash. If you don't want that, you can pay 0 coins to OP_RETURN; that will also work, but it'll cost more.
Or if you are using software which doesn't allow you to do either of these things, then the simplest thing to do is simply change your fee by 1 satoshi.
Why did you say that not miners hold these transactions? Anyone in the network, who have to mine, have to hold it, if I'm not mistaken.
Yes, miners need to know about unconfirmed transactions, but they do so via nodes. Usually what happens is that mining pools run several nodes, and then create candidate blocks which are sent to individual miners. The individual miners themselves don't need to keep their own mempool or run their own node, because the mining pool gathers the necessary data for them via its nodes.