By "middle of the game", do you mean "while the game is loaded" or "on a pre-existing save"?
You can install mods on pre-existing saves, but some mods may not take full effect unless on a newly started play-thru.
You cannot install mods while the game is loaded... I think.
most mods generally can be installed during a play through. I often install new mods and continue to play existing characters. So no. You don't have to start a new character when installing mods.
However some mods, depending what effects or scripts it runs in the game, should not be uninstalled and you continue to play the character. I can't name any specifically but a lot of the times the modder will list uninstall recommendations.
http://www.skyrim.nexusmods.com is the source for mods.
I installed 4 Skyrim HD - 2K Textures, Falskaar and the Unofficial Skyrim patch on a lvl30 Character with no issues its been 2 weeks and my lvl is 52.
hth
like other people said , most mods you can install without having to start a new game however some mods do require you to start a new galme
best advice READ the shole mod description and if still unsure ask in the nexus forums
Overhaul mods would be better off starting a new game with, especially ones like SkyRe which make changes to skill trees and perks. Obviously ones like new races and anything that affects the start should also be on a new game.
Everything else should be fine, but read the readmes and installation instructions for any mod that you install. Some may require a new game due to certain scripts that start at character creation for example.