I know my way around WordPress’ database pretty well and I would never call editing user permissions via PhpMyAdmin an easy thing to do. You are editing serialized strings– very easy to get wrong, actually. So don’t feel bad. There is something very wrong with that statement that “he should easily know how to … edit user(s) as necessary to provide any permissions.”
I can’t promise this will work, but my administrator account on a relatively new install has this in the $wpdb->postmeta table…
a:1:{s:13:"administrator";b:1;}
… under the key wp_capabilites.
Find the wp_capabilities key associated with your (desired) admin user and past that into the meta_value column. Very quick and course testing suggests that should give your user all permissions. That is was able to elevate a “subscriber” to an admin that way. Be careful not to break that serializations. It has to be exactly like that to work. Change one character– for example change one digit of 13 to make it 12– and it will break and you will be looking at a “you don’t have permissions” page.
However, that assumes that he “removed the Plugin & Settings menus” by editing permissions. I have my doubts. Had he done that it should be easy enough to put things back by way of the “User” form.
My guess would be that there is a mu-plugin file doing this (certainly what I’d do). Look in /wp-content/mu-plugins/ and see what you can see.
I’d also guess that if he’s twitched the database like you suspect, he’s twitched it in other ways as well.