You can set something like this up on any VPS with gitolite (https://github.com/sitaramc/gitolite) pretty easily. gitolite lets you set up very fine-grained per-user/repo/branch permissions, manage your users' SSH keys, and gives you nice clean git@git.you.com:repo-name access to your remotes.
I've done this for myself with a $48/year VPS from prgmr.com specifically because I needed more private repos than Github could offer (my setup instructions are here: https://gist.github.com/1035834).
Granted, if codeplane.com existed six months ago I probably wouldn't have bothered with gitolite. It appears they do nice things for you like backups.
Gitosis does not have as fine grained control as gitolite nor is it as well documented (config file errors are hard to debug), but it works well within its limitations. Both are now available as Debian/Ubuntu packages (gitolite was not when I started using gitosis). The other obvious difference is that gitolite is written in Perl and gitosis is written in Python. This should be a superficial difference, but sometimes the world isn't rational.
Gitolite is a fork of Gitosis that has been both improved and actively maintained. It even has a script to automate converting your old gitosis.conf to the new format.
One other thing to point out is that Gitosis is abandonware (last commit was made in September of 2009).
Gitolite on the otherhand is under active development, the documentation is great, and the author is generally available on the #git channel as are many other active users of the software.
Would there be a market for gitolite/gitosis hosting? Say, $1/mo for up to 1G of space, backed up, unlimited private/public repos, cli only, rudimentary web viewer for public repos via gitweb.
It's rather easy to set it up (as the comments here suggest), but seems like a lot of folks wouldn't want to go into trouble of learning about it and/or setting it all up properly, or don't have a server to put it on.
This is worth a try. Make sure you reach break even rapidly so you don't get stuck in burning money. If you already have a server available, then this is pure profit.
This is also a good opportunity to practice startup launching. Identify your target clients, where they are, what they are looking for, etc. Create a landing page with MVP offer description and subscription for availability notification. Check patio11's advices on optimizing the landing page. Then spread the word. The subscription feedback should give you a traction feedback. This should be enough to deduce the fee to reach break even as you launch. Assume only a percentage of subscribers will make the jump. If you can break even with only 10% subscribers adopting it, then things are sound.
Gitolite suffers from being well documented for an open source project yet still very hard to understand from a standing start - it's just not a very intuitive setup. I wrote a post on setting it up just to help me wrap my head around it.
I do this (also on prgmr) and manage backups with tarsnap+cron which with all my small repos costs nearly nothing even if I don't clean up old tarsnap archives.
I've done this for myself with a $48/year VPS from prgmr.com specifically because I needed more private repos than Github could offer (my setup instructions are here: https://gist.github.com/1035834).
Granted, if codeplane.com existed six months ago I probably wouldn't have bothered with gitolite. It appears they do nice things for you like backups.