Have you looked at phpMyAdmin? It's kind of large, but not too hard to install... I find it to be the most useful tool. You can do EVERYTHING with it...
By the way, my host has a similar restriction, but they enable us to work with our databases through phpMyAdmin. And they make it available to us through our domain control panel. It's very convenient. Perhaps you should recommend to your provider that if they don't allow telnet for security reasons, perhaps THEY should give you access to phpMyAdmin...