I'm not sure what you've tried to do before, but here's what I just did and had success:
1) Downloaded the Tomcat 5.5.27 Windows Service installer and installed it.
2) Dumped the TomCat5 service security descriptor using "sc sdshow tomcat5", which showed me:
D:(A;;CCLCSWRPWPDTLOCRRC;;;SY)(A;;CCDCLCSWRPWPDTLOCRSDRCWDWO;;;BA)(A;;CCLCSWLOCRRC;;;AU)(A;;CCLCSWRPWPDTLOCRRC;;;PU)
This is a pretty common security descriptor for services. I've seen it verbatim on some Microsoft services. The SYSTEM and built-in Administrators have "full control", "Power Users" can stop, start, and pause the service, and "Authenticated Users" can query properties of the service (I'm glossing over a bit here).
3) I created a limited user called "bob" on my box, opened a "RUNAS" command-prompt as him, and got his SID from "WHOAMI /ALL" (a command that's on Windows Server 2003 but not on XP... don't know about Vista and Windows 7 off the top of my head). I verified that Bob could not stop / start the Tomcat service (using "NET STOP tomcat5"). I received the same error you report in your post.
4) From my regular administrator command-prompt, ran the following:
sc sdset tomcat5 D:(A;;CCLCSWRPWPDTLOCRRC;;;SY)(A;;CCDCLCSWRPWPDTLOCRSDRCWDWO;;;BA)(A;;CCLCSWLOCRRC;;;AU)(A;;CCLCSWRPWPDTLOCRRC;;;PU)(A;;RPWPDT;;;S-1-5-21-1409082233-484763869-854245398-1009)
This SDDL string gives Bob's SID (S-1-5-21-1409082233-484763869-854245398-1009) rights to stop, start, and pause the service (RP, WP, and DT, respectively).
5) I flipped back to my "Bob" command prompt and verified that I could now stop and start the service using NET STOP and NET START.
I'd recommend creating a group to delegte this right to, putting a user in that group, getting the group's SID (using WHOAMI or any other tool) and modifying the security descriptor this way.
I would think that using Group Policy to modify the security descriptor would work fine. 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.
If you want more background on security descriptors for services, have a look at http://msmvps.com/blogs/alunj/archive/2006/02/13/83472.aspx and http://support.microsoft.com/kb/914392.
Best Answer
Since you've already know about SetACL, and how to use it to allow a user to control a service, you could simply use Scheduled Tasks to regularly run SetACL.
Configure the task to repeat in an interval as small, as the longest acceptable time the user cannot control the service, after a re-installation.
Edit
As you say, it is kind of hacky ;).
Another option, as Adam mentions, is to use GPO's to enforce your ACL.
For a non-standard Windows services, you will have to install and run the Group Management Console, on the computer where the service is installed. Then do the following: