I built a system last year which used Gitorious and Redmine. You can integrate git directly with Redmine, no problems there but I would strongly suggest you have a look at Gitorious as well as the tool to control your repositories and follow their events. It can also be used to control access to the repositories etc.
Integrating Gitorious and Redmine is pretty simple. I wrote a script that unhashes the Gitorious paths. They are saved in the file system hashed when you use Gitorious so linking those repositories to Redmine would be a bit complex otherwise. My script makes links to those repositories in a much more readable format so linking them to Redmine is really simple, and only required once when you create the project. You can find the script here.
Basically you don't need to worry about the integration a lot since Redmine supports git out-of-box - sort of. Of course you need to have the git service running on the server where you "production" repositories are (those that you link to Redmine, do your automated tests etc), but this is also solved with Gitorious.
I actually wrote my Bachelor's thesis about this issue. It's already slightly outdated since both Gitorious and Redmine have developed a lot, but I could make it available if you want to read it. The thesis explains what needs to be done (some of the problems have already been solved by the two tools) and it also includes a continuous integration environment which automatically builds packages when users push changes to the repositories and puts them into a reprepro repository where testers etc. can easily download them with a web browser.
Redmine had some issues last year, especially the lack of sub-projects was a bit annoying but that has been rectified in the 0.9 version. Also the plug-ins should be tested well before taken into production use, some just don't mix well and some don't work at all (probably a clash of Redmine version vs. plug-in version). All in all, though, Redmine works pretty well and should be easily expandable to your needs. Support for Gitorious is superb, for Redmine a bit more sporadic (damn French?) but both tools have large enough user bases that they should be safe bets.
Git is a very good version control tool especially for agile teams. It takes some learning and you should write a guide on how to use it for your developers to get the most out of it, but once you learn it, it's extremely productive. We wrote our own which just states the normal working process. Branching, merging etc. should be explained, for instance working on your personal repository's master branch is not such a good idea. Always create a branch and work there. When you pull changes to your master branch from some other repository, it's easier to handle the merging this way - and you won't accidentally push something you didn't mean to.