Some custom dialer apps (for example, Dialer from MotoBlur) are able to do USSD requests. Is it realy impossible to do this via SDK?
You can dial ussd requests like any other number with an call-intent like this one:
String encodedHash = Uri.encode("#");
String ussd = "*" + encodedHash + "12345" + encodedHash;
startActivityForResult(new Intent("android.intent.action.CALL", Uri.parse("tel:" + ussd)), 1);
However, afaik, it's currently not possible to parse the result string in your app.