I have read that once a Bitcoin transaction is created, it never automatically expires. In theory, a transaction could be created, get stuck at 0 confirmations for some years, and then all of a sudden confirm.
The proper way of increasing the fee would be to send another transaction that uses exactly the same coins as the first transaction.
How can I program the correct way via bitcoind? Which commands should I use?
You can use Opt-in Replace By Fee to do this. Bitcoin Core already implements support for signaling Opt-in RBF and for increasing the fee later (with some caveats).
When creating a transaction from the command line, the send* commands have an optional argument named replaceable. If you set that to true, then the transaction created will automatically signal that it can be replaced in the future. To increase your fee, you then use the bumpfee command. Note that the command currently only works if the transaction has a change output. The fee will be deducted from the change output.
Note that these commands and the arguments are not necessarily listed on the bitcoin wiki (it is frequently out of date). To actually get the full listing of RPC commands, their arguments, and how to use them, use the help and help <command> commands.
