I want to make a clean installation without the OEM software, but
I can't seem to see the CoA sticker with the Windows 7 key on the
bottom of the computer.
Is this supposed to be this way? How can I obtain my license?
Depending on how you ordered it this might have been the way it was intended.
If you ordered Windows 7 professional 64 bit as a full product to be bundles with your installation (and the price rose a 100 Euro-ish) then no. You should have a proper working CoA sticker.
If you just selected 'windows 7 prof x64' from a menu while configuring the laptop then you probably ordered thre OEM version. That one is usualy activated by a key in the BIOS and there is no need to actually ship a laptop with a CoA.
Despite this many laptops ship with a OEM installed OS version, a matching key in the BIOS and a CoA. To use this CoA you will need the matching regular ISO and not the OEM prepped version.
OK, with all this background out of the way: CoA tended to get worn down. Putting some tape over it helped, but most were still unreadable after a year or five. Many manufacturers solved this problem by moving the CoA to a different place than the bottom of the laptop. In the case of your laptop it is behind the battery.
Also, is it recommended to have a clean installation and get rid of
the Lenovo software stuff>
Yes. Yes it is.