En CentOS, no se necesita ningún paquete adicional:
python -c "import urllib;print urllib.quote(raw_input())" <<< "$message"
Extendiendo la muy útil respuesta de Rockallite para Python 3 y la entrada multilínea desde un archivo (esta vez en Ubuntu, pero eso no debería importar):
cat any.txt | python3 -c "import urllib.parse, sys; print(urllib.parse.quote(sys.stdin.read()))"
Esto dará como resultado que todas las líneas del archivo se concatenen en una sola URL, las nuevas líneas se reemplazarán por %0A .
Quieres $MESSAGE estar entre comillas dobles, para que el shell no lo divida en palabras separadas, luego lo pasa a PHP como argumento:
ENCODEDMESSAGE="$(php -r 'echo rawurlencode($argv[1]);' -- "$MESSAGE")"