I have played around 300 hours now of Skyrim with my character and is around level 80. I still have TON of stuff and quest left to do though. I really would like to spice things up at this point, while still being able to continue with my game and my quests without having to start over.. I am using a bunch of mods already but they are all just visual (graphics, Hud, menus)

I heard about Skyrim Redone and how it is supposed to make the game feel very fresh and a lot harder. I also heard you have to start a new game to use it though? Is there any way around that? I heard it was kind of modular so is it possible in any way to insert into my game so I can just continue on but with its changes?

I think it is supposed to change the whole skilltree though, so that might be a problem, but maybe it is possible to just reset my skillpoints and allow me to spend them in the new skilltree?

Or is it possible to start a new character, but still keep your progress in the game? Like you have a new character, but the map is still as it was before, with all the places you have cleared and quest completed and so on?

Lastly, how different is Skyrim Redone really to vanilla Skyrim you who have played it?

You should not have a problem adding Skyre to your game, though being at level 80 already you will likely miss out on much of the increase in difficulty. Just follow the directions on setting it up. It even has a means and directions for redistributing your perk points to the redone perk trees! I have never payed a vailla set up so I can not comment much on the differences it will make epecially if you are already high level character. As always make a hard save in an interior before adding in new stuff.

I do not think it will work that well since the mod is more designed around starting a new character.

You can use it in an already existing save but after you install you should go to an interior with no npc's, like your player home, and wait 30 days ( or whatever your cell reset time is). This should update most npc's in the world, although I'm not sure if it will update the stats for unique non respawnable npc's. SkyRe will also give you a potion of respec that will give you all of your perk points back so you can reperk according to the new layouts. Again at level 80 you will miss out on alot of what makes SkyRe so fun, but enemies should still be harder than vanilla. Also SkyRe's perks go up to lvl 150.

Ok thanks! How about Requiem and Frostfall? How friendly are they to use on a previous game? And about Frostfall, does it add a lot of bad weather and snow? (I kind of like the more summer looking Skyrim, and are using some graphic mods that make it more lush and green)

According to what I read up on Requiem, you can't use it on an existing save, you have to start a new character.

With Frostfall you should not have any problems with an existing save. I added many hours into one of my old saves, but had to tweak the .ini because the scripts were running slow. (Don't know if that was related) It doesn't add new weathers, rather it adds different Exposure rates depending on which region of Skyrim you're in. For more weathers, mods like Climates of Tamriel or Enhanced Dynamic Weather System is what you're after. Check out the author's page for Frostfall for all the info you need.