How to forcibly create/modify MySQL user grants, without restarting the database service
You could copy just the the "mysql" database away to another location and start another daemon on it.  Get the SHA1 or DES hash stored in the user table for a user with SUPER privs (usually root, but sometimes renamed for security through obscurity).  

Then connect to the mysql using a modified version of the client library that makes mysql_real_connect() support using a pre-hashed password instead of having it take the password plaintext.  This should be trivial.  

You won't ever know the actual password, but with the hash and a modified client you'll be able to log in anyway.

You can then make any modifications to permissions, create necessary schema and tables and flush privileges.  

I'll leave the security implications of such practices up to you.