Waa..thats a lot to do..
Can I just replace my cpu cooler with a new one??
Well, cleaning the dust out of your case will help all your components. As for getting a new heat sink... you'll still need to remove the old heat sink and clean all the old thermal paste off the CPU, then apply new thermal paste and the new heat sink. Depending on the heat sink you get, it may come with preapplied thermal paste.
You can try playing games with the computer cover off, but it won't fix your heat issue. Your CPU will also have a shortened lifetime due to excess heat.