For Ubuntu 14.04 and Android try:
hcitool scan #get hardware address
sudo bluetooth-agent PIN HARDWARE-ADDRESS
PIN dialog pops up on Android device. Enter same PIN.
Note: sudo apt-get install bluez-utils
might be necessary.
Note2: If PIN dialog does not appear, try pairing from Android first (will fail because of wrong PIN). Then try again as described above.