The answer is Replace-By-Fee.
Replace-By-Fee (RBF) is a recently reintroduced feature to allow a sender "bumping" the fee of a "stuck" transaction.
In reality, a new transaction with the same outputs and inputs is created. The only difference is that the sender is able to include a higher fee as an incentive for miners to include such transaction in a block faster.
For the purpose of the tutorial, I'll be using Electrum 2.8.2. The process should be very similar in other wallets that support RBF feature too.
Before making any low-fee transaction, make sure Replace-By-Fee option is turned on.
Tools -> Electrum preferences and change Propose Replace-By-Fee to Always or If the fee is low.
Say you want to try your luck paying a 0.0001 BTC fee first (just to find out it's insufficient and your transaction won't be confirmed anytime soon).
Choose the Replaceable option and send the transaction.
The transaction will be placed in Mempool which is a list of unconfirmed transactions.
The size of Mempool is currently huge and it may take up to several days for some low-fee transaction to be confirmed.
You can check the Mempool size at blockchain.info.
Back to Electrum now.
Unconfirmed RBF transactions are clearly distinguished from non-RBF ones with a yellow triangle and label Replaceable.
Wait for the transaction to confirm within an acceptable (for you) amount of time.
If it doesn't, right click the "stuck" transaction and select Increase the fee. A window will popup with an option to raise the fee.
Move the slider back and forth to get new confirmation estimates.
You can also calculate the "sufficient" fee yourself using data from 21.co.
In this particular case, paying anywhere between 201-220 satoshi per byte should be good enough to get the transaction confirmed within next 25 blocks or roughly 4 hours.
To calculate the total needed fee click OK. Transaction details will pop up (don't hit the Sign button yet).
Look for the transaction Size which is 226 bytes in our case.
Multiply this size with a chosen fee rate and you'll get the total fee that needs to be paid, let's say:
226 B x 220 satoshi = 49 720 satoshi or 0.0004972 BTC
Close the window and go back to the "RBF screen".
in the New fee field, type in the new fee denominated in BTC (0.0004972 BTC) and hit OK.
Click Sign and then Broadcast to send the new transaction.
The former transaction will be replaced by the new one which should hopefully be picked up by miners soon.
Please note, that when you look up the new transaction on a block explorer like blockchain.info, it will warn you that it's a possible "double spend" of a previous transaction.
While RBF makes it easier for non-tech folks to double spend an unconfirmed transaction, it's almost equally trivial to do so even without Replace-By-Fee turned on.
Therefore, it's highly recommended to never accept any unconfirmed transactions for this reason alone.
I hope your Bitcoin experience is mostly positive but Replace-By-Fee was put in place in case it's not.
The rule of thumb is to have it turned on by default for all transactions. The reason is that Mempool can grow within a few minutes and what seems like an adequate fee will quickly become insufficient.
If you're paying your business partners for goods and services or sending other important transactions (e.g. rent) you don't want to take your chances.
Will you start using Replace-By-Fee from now on? Please let us know in the comments below.