Run commands “without” terminal

Alt + F2 worked for me (i know you suggested it didn't work for you, however its worth reinforcing for others!).

Kubuntu 15.04

This type of GUI for running commands is basically known as "Run" interface. It's fairly simple idea.

In the Ubuntu's Unity environment Alt+F2 allows running specific commands using the default shell, dash or Debian Amquist Shell. Of course, you have to remember that you are running commands "blindly", meaning without the STDOUT output from command or STDERR streams going. So unless you are running a GUI app, you won't know if your command failed or not.

There are tweaks for Gnome desktop environment to utilise the same keybinding as well, which if I am not mistaken , can be configured using from Gnome Tweak Tool

For blackbox desktop environment there exists bbrun package, which also does very much the same functionality.

At the very bottom of things, one could build such tool by themselves, using any programming language available or desired. For instance, here's some examples

Shell script + zenity

#!/bin/sh
exec $(zenity --entry --title "Enter command" --text "") 

Java:

//runSomething.java
import javax.swing.JOptionPane;
import java.lang.Runtime;
import java.io.IOException;
public class runSomething
{
 public static void main(String [] args) throws IOException
 {
  String cmd = JOptionPane.showInputDialog("Enter command:");
  Runtime.getRuntime().exec(cmd); 
 }
}