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:
- Wait for facebook to implement the dialog for android.
 
- Try to open the dialog in a browser (the url for that is in the docs) in the mobile device.
 
- Ask for the 
xmpp_login and add a xmpp client (i.e.: asmack) and with that you can implement your own "Send Message" dialog.