The fundamental problem you have is this:

You cannot grant another user a privilege which you yourself do not have; the GRANT OPTION privilege enables you to assign only those privileges which you yourself possess.

^{— http://dev.mysql.com/doc/refman/5.6/en/grant.html}

This makes sense, since if it were otherwise, then you could just grant privileges to yourself.

There is one way around this, depending on how much flexibility you have with the calling code -- stored procedures can run with the credentials of the defining user (as opposed to the invoking user). If the calling system could call a procedure instead of using GRANT ..., then you can create a procedure that is executable by the restricted user, granting other privileges as appropriate.

I have dealt with this issue before.

When you ran

select count(1) UserTableColumnCount from information_schema.columns
where table_schema='mysql' and table_name='user';

you should have gotten 42. That's how many columns MySQL 5.5 has for mysql.user. Since you got 39, that means you must have upgraded from MySQL 5.1. That has 39 columns.

I wrote an earlier post about the number of columns in mysql.user in different versions : MySQL service stops after trying to grant privileges to a user

Here is the post where I dealt with this : mysql: Restore All privileges to admin user

Hopefully you could run

# mysql_upgrade --upgrade-system-tables

to realign mysql.user and have it autofill missing permissions with Y.

Give it a Try !!!

If you want to try to fix the mysql.user manually, here are the steps:

#
# Backup the mysql.user table
#
CREATE TABLE mysql.user_backup LIKE mysql.user;
INSERT INTO mysql.user_backup SELECT * FROM mysql.user;
#
# Add Missing Columns
#
ALTER TABLE mysql.user 
    ADD COLUMN Create_tablespace_priv enum('N','Y') NOT NULL DEFAULT 'N'
    AFTER Trigger_Priv
;
ALTER TABLE mysql.user ADD COLUMN plugin char(64);
ALTER TABLE mysql.user ADD COLUMN authentication_string text DEFAULT NULL;
#
# Give root user all privileges
#
UPDATE mysql.user SET
Select_priv='Y',Insert_priv='Y',Update_priv='Y',Delete_priv='Y',
Create_priv='Y',Drop_priv='Y',Reload_priv='Y',Shutdown_priv='Y',
Process_priv='Y',File_priv='Y',Grant_priv='Y',References_priv='Y',
Index_priv='Y',Alter_priv='Y',Show_db_priv='Y',Super_priv='Y',
Create_tmp_table_priv='Y',Lock_tables_priv='Y',Execute_priv='Y',
Repl_slave_priv='Y',Repl_client_priv='Y',Create_view_priv='Y',
Show_view_priv='Y',Create_routine_priv='Y',Alter_routine_priv='Y',
Create_user_priv='Y',Event_priv='Y',Trigger_priv='Y',
Create_tablespace_priv='Y'
WHERE user='root';
FLUSH PRIVILEGES;

That's it !!!