Can you install Linux on a Raspberry Pi without needing an HDMI-display?

Yes, you can do this at least with Arch Linux. After you build the microSD flash card filesystem on some other computer, you can boot the RasPi with that microSD card and an ethernet cable plugged in. Arch Linux will boot, acquire an IP address with DHCP. You log in as either root, or a plain user over ethernet, so you have to figure out what IP address the RasPi is listening on.

Raspbian from early 2016 allows ssh after second boot.

First boot from SD resizes partitions and generates sshd keys, but doesn't start ssh daemon.

Wait 5-10 minutes and powercycle RPI. Connect over ssh using default credentials.

Finding RPI's ip address is out of scope of this answer :)

Update 2017: raspbian stretch doesn't require powercycle, but needs a file 'ssh' placed in root of smaller SD card partition

You can setup a Raspberry Pi without using a monitor/keyboard/mouse and even without a network connection using PiBakery, a blocks based setup tool that allows you to configure settings, modify files, and install software before you even write the SD card.

Once you've set what options you want, you can then write your SD card with your configurations, and your Pi will be setup on first boot.

Learn more at www.PiBakery.org

_{^{Disclaimer: I wrote PiBakery}}