It is not possible to send private messages on the behalf of the user using the graph api.

You should however be able to use the Send Dialog, though I haven't tried it on android, but it should be something like:

Bundle params = new Bundle();
params.putString("to", "USER_ID");
params.putString("name", "TITLE HERE");
params.putString("link", "A URL"); // this link param is required

facebook.dialog(context, "send", params, new DialogListener() {
    @Override
    public void onComplete(Bundle values) {
       ....
    }

    @Override
    public void onFacebookError(FacebookError error) {}

    @Override
    public void onError(DialogError e) {}

    @Override
    public void onCancel() {}
});

Another approach you can use is the Chat API with which you can send messages on the behalf of the user, it requires the xmpp_login permission and you to implement an xmpp client.

Edit

Since this dialog is not supported yet in android, you have 3 options:

1. Wait for facebook to implement the dialog for android.
2. Try to open the dialog in a browser (the url for that is in the docs) in the mobile device.
3. Ask for the xmpp_login and add a xmpp client (i.e.: asmack) and with that you can implement your own "Send Message" dialog.