You can definitely use Group Policy to grant users rights to start / stop services. You just need to modify the security descriptor on the service using the "Security" group policy client side extension.
A very slight caveat: I have seen cases where some services don't like the default permission that a group policy-based modification puts on a service (look at this posting about the Windows Search service if you want to see what I'm talking about: http://peeved.org/blog/2007/12/07), but that has been uncommon in my experience.
In order to "see" the service in the Group Policy editor you'll need to do the editing on a computer that has the service installed. (If this is a stock Windows service then it's no big deal, but if it's something third-party get on a machine that has it installed, "runas" a copy of MMC, and snap-in a Group Policy editor targeted at the GPO where you want to put these settings.)
Under "Computer Settings", "Windows Settings", "Security Settings", and "System Services", locate the service you want to grant start / stop permission to and define a policy setting. You have to choose a startup type. Click "Edit Security" and modify the default ACL to include the permissions you're looking for.
I'd recommend testing the GPO on a constrained group of computers (either by linking the GPO to a test OU with a single computer, or by filtering the GPO to only a single computer) and making sure it does what you want before you go changing the security on all your computers only to find out it doesn't do what you want.
Here's some background on what the various entries in an ACE mean for services:
To see the descriptors in SDDL notation, use the "sc sdshow service-name" command.
Delegated permission to create new services is going to be a little bit tough. There is a "SC_MANAGER_CREATE_SERVICE" right that can be granted to users on the service control manager (SCM) object in the global object manager.
In Windows versions up to Windows Server 2003, the rights could not be changed on the SCM. Starting in W2K3 SP1, you could change the rights on the SCM.
The API to change the security is SetServiceObjectSecurity, and more information is available here: http://msdn.microsoft.com/en-us/library/aa379589%28VS.85%29.aspx
Some more reference re: the rights that can be granted to the SCM and the default DACL set on the SCM is available here: http://msdn.microsoft.com/en-us/library/ms685981%28VS.85%29.aspx
In short, there's no way to do this w/o writing code. There's no magic registry setting, etc. If you can get somebody to write the code for you, though, it's totally feasible.