Increase transaction fee with Bitcoin Core client fails because of no change output. Why? Context

I created a transaction (using the full balance of an output) with the Bitcoin Core Wallet (running as full node). The transaction got into the mempool of major nodes, as expected. I set the fee to what the client recommended for a slow transaction (little more than 9 sat/B) , but these days this turns out to be very low. Given the current state of the mempool at hoenicke this may get confirmation in weeks, if at all.

Increasing the fee fails

I initially, deliberately, set the transaction to "Request Replace-By-Fee", and I want do increase the fee now. I expected to take some part of the "target amount" and use it as fee, leaving the total amount of the transaction the same (still spending the complete output in total)

However, this does not seem to be possible by design. I get a "Fee bump error" saying "Increasing the transaction fee failed (Transaction does not have a change output)".

What to do about it?

Why am I not able to change the target/fee balance of a transaction, and how am I expected to increase the fee at this point?

Transaction Details (as per Request)

Summary
Size    1xx (bytes)
Weight  7xx
Lock Time   Block: 49xxxx

Inputs and Outputs
Total Input 0.01xxxxxx BTC
Total Output    0.01xxxxxx BTC
Fees    0.00001xxx BTC
Fee per byte    9.xxx sat/B
Fee per weight unit 2.xxx sat/WU
Estimated BTC Transacted    0.019xxxxx BTC


Both input and output addresses start with "1"
BIP125 RBF (Replace-by-fee) transactions in bitcoin-core 0.15.0.1 appear to require a change address with a balance in order to facilitate a future RBF-based fee increase.  

By way of an example, consider the following transaction:

Input  - 1.00000 BTC
Output - 0.99998 BTC
Fee    - 0.00001 BTC
Change - 0.00001 BTC


Assume the fee is too low.  Now, we want to increase the fee for the transaction, so the RBF replaces the prior transaction with one like:

Input  - 1.00000 BTC
Output - 0.99998 BTC
Fee    - 0.00002 BTC
Change - 0.00000 BTC


Now the fee is enough that the transaction is confirmed.

Without "change" present in the first transaction, there is no source for the increased fee.  RBF could be implemented such that the output is reduced to allow for a greater fee; I'm not sure why that is not supported.  Line 2928 of the wallet.cpp source code in the bitcoin-core github repository states:

break; // Done, able to increase fee from change


The way around this problem for a transaction that has RBF enabled, but has no change address is to follow the directions contained in one of the answers in the canonical "transaction not getting confirmed" question.  I experienced the exact issue last week and was able to successfully recover using the -zapwallettxes option in the bitcoin-core wallet CLI.