The node itself and it's peers are responsible for how long a transaction stays in pending. It used to be (April / May 2017) that a transaction would be removed from the queue after ~3hrs or it could be replaced by a transaction with a higher gas price. A transaction will also be removed if it becomes invalid (e.g. you no longer have enough ETH in your account to send the transaction, the nonce of that transaction has already been used, etc.
Due to overwhelming amounts of pending transactions during ICOs, many public nodes (etherscan, MEW, infura) adjusted their settings in order to keep more transactions in a pending state for a longer period of time. Shortly thereafter, geth and parity made updates to the default settings and the control individuals had.
How long to wait before re-sending the transaction.
If you try to send again, it is possible that the transaction will be sent twice, or unexpectedly. This is due to the
nonce value that you give any transaction. The new transaction cannot be mined until the previous transaction is mined. If there is a point in time where the first transaction is removed but not the second one and then you attempt to send a third transaction, you could end up sending the third transaction and then the second transaction. Or, both transactions could go through.
What you want to do is replace the transaction with a no-value transaction from yourself, to yourself in order to remove the previous transaction from pending. Then you can attempt to resend the original transaction with higher gas.
You can do this via https://www.myetherwallet.com/#check-tx-status, if you can find the pending transaction in MEW, Etherscan, or Infura's pending pool. You can switch between the three aforementioned nodes by using the "Network" dropdown in the upper-right corner.
How do I track whether pending transactions will no longer be mined and trigger re-send transaction?
See above, but I would also like to note that it is possible that a transaction can be pending in a node that is not one of the above three but is still in the queue somewhere.