My proc info:

 lscpu
Architecture: x86_64
CPU op-mode(s): 32-bit, 64-bit
Byte Order: Little Endian
CPU(s): 4
On-line CPU(s) list: 0-3
Thread(s) per core: 1
Core(s) per socket: 4
Socket(s): 1
NUMA node(s): 1
Vendor ID: GenuineIntel
CPU family: 6
Model: 158
Model name: Intel(R) Core(TM) i5-7400 CPU @ 3.00GHz
Stepping: 9
CPU MHz: 1036.788
CPU max MHz: 3500,0000
CPU min MHz: 800,0000
BogoMIPS: 6000.00
Virtualization: VT-x
L1d cache: 32K
L1i cache: 32K
L2 cache: 256K
L3 cache: 6144K
NUMA node0 CPU(s): 0-3

I tried:

sudo apt-get install gcc-arm-linux-gnueabi g++-arm-linux-gnueabi

If I go for:

arm-linux-gcc
arm-linux-gcc: command not found

How to install cross-compiler?

TLDR

you need to call arm-linux-gnueabi-gcc not arm-linux-gcc.

It looks like you've just got the wrong file name. For reference apt-file is a useful tool.

sudo apt-get install apt-file
sudo apt-file update
apt-file search -x 'gcc$' | grep 'gcc-arm-linux-gnueabi'

This searches any file ending gcc in any package with gcc-arm-linux-gnueabi in the name. The result is:

gcc-arm-linux-gnueabi: /usr/bin/arm-linux-gnueabi-gcc

So if you have installed gcc-arm-linux-gnueabi you should have a file /usr/bin/arm-linux-gnueabi-gcc.

As steeldriver suggests, you already have installed the cross-compiler; the problem is that you’re using the wrong command to invoke it, you need to use the arm-linux-gnueabi- prefix in general. So run

arm-linux-gnueabi-gcc

or

arm-linux-gnueabi-g++

and it should work fine.

To figure this out yourself, you can use dpkg -L to list the contents of the packages you’ve installed:

dpkg -L gcc-arm-linux-gnueabi