You probably have the wrong path for --with-pg-config, check if it’s actually there.
You can find the correct path to pg_config with:
find /Applications -name pg_config
In the latest Postgres.app Version the path is:
gem install pg -- --with-pg-config=/Applications/Postgres.app/Contents/Versions/9.5/bin/pg_config