Generate address (for receiving) on GNU/Linux without Bitcoin client? If I understand it correctly, I could generate a valid Bitcoin address (key pair) following this algorithm. 

With an address generated in such a way I would be able to receive Bitcoin without ever having to install a Bitcoin client. Is this correct?

How could I follow this algorithm with common (command-line) tools, i.e. those typically available on (even older) GNU/Linux systems? (they don’t have to be installed by default, but they should be part of the distributor’s package archive)

Would there be any risks/problems using such a key instead of one generated by a Bitcoin client?
I recommend simply using vanitygen like this:

vanitygen -1 1


This will generate a small number of addresses that you can use, as well as their private keys.

vanitygen is trivial to install on any POSIX system and is proven to work.

Alternatively, you can try bitcoin-bash-tools. Source that from your .bashrc or simply run it, then you can create a new keypair with newBitcoinKey.