You can't create a new private key without creating a new address.

They are linked and can't be separated.

Seems about right...
Now, to answer your questions:
You'd need to rescan the complete blockchain, but not redownload it. Rescanning can take a couple of hours, but everything depends on your cpu, memory and IO speed of your disk.
The best fee depends on the number of unspent outputs that are managed by your wallet (1). I wrote a tool long ago to help you with this task: https://www.mocacinno.com/page/feeestimate
If you have the number of inputs/outputs OR a list of funded addresses managed by your wallet, this tool will help you estimate a reasonable fee. However, if you keep your wallet open for a couple of hours before creating a tx, bitcoin core should have a reasonable fee estimation automatically.

As for your last question: there are ways to mess this up in a way you cannot fix it by having access to wallet.dat (1). However, as long as you keep 2 secure backups of both wallet.dat's, and you double check the deposit address generated by wallet.dat (2), i don't see a way to really mess things up.

In that case, at this time, i'd recommand a fee of ~0.003, in this case you'll have a very reasonable chance of getting your transaction confirmed within 2-3 hours.
If ~0.003 is to much (personally, i think it's a lot of money), you can always try a little lower fee, however you'll have to expect to wait a longer time.

no, it doesn't make a difference... An unspent output is an unspent output, disregarding which address it's funding.
As for your other question: if you have an idear which addresses are managed by your wallet, you can look those addresses up on a block explorer, even if you don't have physical access to your wallet.

For example: if you look up your address on blockchain.info, you should see a link called "Unspent Outputs". If you click it, you can count the number of unspent outputs funding this one address. If you do this for most (or all) of the funded addresses of your wallet, you know the number of unspent outputs (approximately... It's allways possible you're forgetting some addresses... And it's possible your wallet generated change addresses you don't know about to)

Theoretically, yes... If you were collecting 1000's of dust inputs, the fee can be really high when talking in fiat terms... However, if this is the case, let me know and i'll give you some tips on how to pay a smaller fee.

I was still editing my previous post (re-editing posts is something i like to do when i don't like my initial answer), i think your question has been answered by my edit.
In short: you'll be creating a transaction with x inputs and 1 output... To find the number of inputs, open your wallet ,go to help => debug window => console and type "listunspent" (without quotes offcourse). Now you can count the number of unspent outputs.
If you don't like the fee estimation bitcoin core is giving you, you can put the number of inputs you found by using the command "listunspent" and 1 output in my wizard: https://www.mocacinno.com/page/feeestimate (option 2)

Seems about right...
Now, to answer your questions:
You'd need to rescan the complete blockchain, but not redownload it. Rescanning can take a couple of hours, but everything depends on your cpu, memory and IO speed of your disk.
The best fee depends on the number of unspent inputs that are managed by your wallet (1).

As for your last question: there are ways to mess this up in a way you cannot fix it by having access to wallet.dat (1). However, as long as you keep 2 secure backups of both wallet.dat's, and you double check the deposit address generated by wallet.dat (2), i don't see a way to really mess things up.