It will save you a lot of time and money to change the arduino board instead of looking for a chip replacement.
Option 1 : buy a Mega 2560. Lots of possibilities, compatible with Uno. I have a 1280 and I am found of it. Bought in China/eBay for 20EUR (27USD), cheaper than Uno.
Option 2 : go Maple. I didn't do it yet, but likely my second project will do. Maybe in a "mini" version.
It has many interresting features, such as real USB (not limited to a serial-usb emulation), 32bit, etc.
Not 100% compatible however, look at http://leaflabs.com/docs/language.html
for the differences.
And there are others that are less obvious. For example, "shield compatibility" may be true in theory but an issue if you go from 5V to 3V3.
I would not recommend the liquidware Illuminato stuff because it does not seem it supports everything : I visited the website and its says that millis() is not implemented for example.
Also I could not find any sort of manual/reference other than the page in the "shop". Not good sign. Remember that since this is all open source, any individual can make its
own flavour and sell it. Then you rely on one person for support. Not a good idea for newbies. In open source, better stick with "mainstream" stuff if you want my opinion.
(If not, you still get it). That said, I have nothing against liquidware and others that want to innovate. It's all a give/take approach.
The "upgrade" is for older chips (I think from 16k to 32k), so you're already at the max. Yes you can switch boards in the IDE,
but only between "standard" boards. There are some config files somewhere that pre-define what a specific board is.
Hope this helps.