It is complicated and probably better to look at the code directly as trying to explain it in English at a high level abstracts some of it away so while this gets you closer it may still leave some parts ambiguous.  The second image is closer to the correct scenario however remember a tx can have multiple inputs as well.

A hash of the simplified transaction consisted of a SINGLE INPUT and ALL outputs is created, this is then signed by the private key for that input and stored in the "sig & pubkey" portion of that tx input.  
See here: https://en.bitcoin.it/w/images/en/e/e1/TxBinaryMap.png  

Bitcoin has no concept of "owners" or "wallets" so the change output isn't special, it is an output just like any other.  If you are going to create an illustration for explaining then creating one with only a single input is a poor choice because the next questions becomes how to dI handle n inputs where n >1.  An example with 2 inputs is better because 3, 20, or 4,000 inputs are handled exactly the same as 2.  

The other thing you need to divorce yourself from is you aren't sending funds from a public key, you are using a SPECIFIC unspent output of a prior tx as an input.  Yes in conversation we may say "he paid me from address 123..." but when trying to explain Bitcoin's working that falls apart and trying to understand anything becomes impossible.  An input is a specific unspent output.  It is referred to (in the Tx input) by the tx hash (of the prior tx) and index (which output of that tx is being used here).

So in more general form.   Lets assume you have a tx which consists of 3 unspent outputs (which become inputs for this tx) A, B, C and two new outputs Y & Z (it doesn't matter if one of these is a change address or you just happened to pay two different receivers with the exact amount of coins, an inputs is an input and an output is an output).

First the output scripts are created.  The "normal" Bitcoin tx is a PayToPubKeyHash, so likely the user provided you a Bitcoin Address.  This is reversed into the PubKeyHash and a script which locks that output of a specific value to a specific PubKeyHash is created.  The outputs are arranged in a sequence randomly (to avoid leaking which one is the "change").  Lets say Z become TxOut0 and Y becomes TxOut1.  The inputs are then arranged in a sequence randomly.  Lets say A becomes TxIn0, B becomes TxIn1, and C becomes TxIn2.

We now have a tx which looks like this:
TxIn0
Txin1
TxIn2
TxOut0
TxOut1


A simplified version of the tx is created (TxIn0, TxOut0, TxOut1) and hashed.  The hash is signed by the private key for A and stored in the Sig & PubKey section for TxIn0.
A simplified version of the tx is created (TxIn1, TxOut0, TxOut1)and hashed.  The hash is signed by the private key for B and stored in the Sig & PubKey section for TxIn1.
A simplified version of the tx is created (TxIn2, TxOut0, TxOut1) and hashed.  The hash is signed by the private key for C and stored in the Sig & PubKey section for TxIn2.

One last thing which may not be obvious.  There is no 1:1 relationship between inputs and private keys.  For example if you have two unspent outputs to the same address (say A & C) then they share the same private key however they are still unique and discrete inputs so the tx above would still have 3 inputs.

I likely am overlooking or misstating something here so I would double check all this against the code.

Transaction fees do not have an output address.

Transactions do not specify transaction fees.

Transactions specify inputs and outputs.

If the value of the sum of the outputs is less than the value of the sum of the inputs, then the difference is considered to be a "transaction fee".

When a miner (or mining pool) builds a block, they create a special "coinbase" transaction that has no inputs and assigns outputs to any addresses they want.

To be considered a valid block, the value of the sum of the outputs in the coinbase transaction must be less than or equal to the sum of the current block subsidy (25 BTC right now) plus all the transaction fees of all transactions that were included in the block.

The handling of tx fee is a pretty ingenious solution.  The tx fee and the miner reward are loosely coupled.

There is one potential concern, since tx fees are implied not explicitly defined, a bug in a client could result in a loss of coins for a user.

For example say a flawed client created this tx:
TxIn0 (value 100 BTC)
TxOut0 (value 1 BTC)
TxOut1 (value 9 BTC)

You just paid 90 BTC as a fee to miners.  Likewise a flawed miner could actually "erase" coins permanently.  If the sum of all txs in a block is 1 BTC and the block reward is 25 BTC but due to a bug the miner makes the coinbase tx 25.1 BTC then the money supply would be reduced by 0.9 BTC permanently.

The major clients are at this point pretty extensively tested so the risk is more in custom implementations or using the rawtx RPC call (which is very low level and will let you do lots of dangerous things).

Bitcoin likely can't be changed at this point however for an altcoin the only (hindsight being 20/20) changes I would recommend would be:
a) make the tx fee explicitly defined in the tx header and thus a tx is invalid if the sum(inputs) =/= sum(outputs) + txfee
b) make a block invalid if coinbase =/= sum(tx_fees) + current_block_subsidy

FTFY.

D&T, If you happen to come back to this thread, you may want to edit your post to prevent confusion for others who read it but don't make it this far in the discussion. (As a matter of fact, if I notice that you've fixed your post, I'll delete this one since it will no longer be necessary)