Mandatory reading for an upgrade is:
A) Upgrade guide
B) Release notes
C) README and/or RNs from OVA of target release.
You can upgrade CUC at any point in time, the answer to your sequencing questions around CUCM and IM&P are covered in the above documentation, as well as the whole procedure, pre-reqs, post-upgrade checkst, etc.
As to licensing, yes, assuming you have your contracts in place to perform the major upgrade, you can reach out to licensing to get your 9.x licenses into 11.x licences.
HTH
java
if this helps, please rate