How to connect two Arduino without shields?

There are two categories i can think of to classify comminucation features of the Arduino boards:

Between 2 devices:

• Serial: Easy to use and only requires 2 data lines.
• OneWire: Harder to use and slow, but uses only one data line

Between more than 2 devices

• I2C: You can have up to 128 devices on a network, individually addressable, but requires a master device, uses 2 data lines. this is know also as Wire.
• SPI: difficult to use, but very fast and easy device selection. uses a lot of data lines (3 + num of devices)
• OneWire: using addressed oneWire is even slower than regular oneWire, still only one data line
• SoftwareSerial: You can have several devices connected by different Serial lines, but it is slower.
• CAN: only available on the Due, and addressable

There are other methods available, but these listed only require a minimum of external hardware.

For distance ratings, see http://forum.arduino.cc/index.php?topic=82937.0 and http://www.tldp.org/HOWTO/Remote-Serial-Console-HOWTO/serial-distance.html

These data rates are directly controlled in Serial and can be tweaked in many others.

For long distance wired communication, look at RS-485.

Since it uses a differential balanced line over twisted pair (like RS-422), it can span relatively large distances (up to 4,000 feet (1,200 m)). A rule of thumb is that the speed in bit/s multiplied by the length in meters should not exceed 108. Thus a 50 meter cable should not signal faster than 2 Mbit/s

You can use the MAX485 chip. It's pretty easy to work with but there's a good library as well:

https://github.com/Protoneer/RS485-Arduino-Library

Freakduino makes some Arduino boards with built in wireless. Their long range wireless is 900 MHz and their shorter range is 2.4GHz. I think they are actually XBee radios and for programming you would use a library called chibiArduino, which is available (and documented) on the Freakduino website. When communicating wirelessly with another radio you can use Broadcast or specify a radio by it's ID which is a value you need to set in the EEPROM of the Freakduino.

Taken directly from the Freakduino site:

The addition of an integrated wireless radio based on the IEEE 802.15.4 protocol (same radio protocol as the XBee) allows for wireless control of devices or wireless sensor data collection. Optional battery circuitry was added so that it could function as a true wireless node without any external power cables. The board is also designed to fit a ruggedized enclosure so that the design can be transported safely or deployed in an actual usage scenario without worrying about damaging the circuitry.

This 900 MHz radio is a personal favorite of mine. I use it all the time because 900 MHz offers much better range compared to 2.4 GHz. The radio can output up to 10 mW of transmit power which can get a surprising amount of range. With direct line of sight, a few hundred meters would not be surprising. If additional range is needed, the modulation mode can also be changed from OQPSK to BPSK. This results in additional range at the expense of data rate, with the max going from 250 kbps to 40 kbps in standard mode.

Like you said, Ethernet shields are expensive, but you don't have to use the shield. Check out the enc28j60 for wired networking, or the ESP8266 if you would prefer wireless. Both are about $4USD. I am using the ESP8266 now and have about 8 devices talking to each other and a Raspberry Pi. It is a really great little chip! I cannot speak personally to the ENC28j60, as they are still sitting in the package on my desk.

You could use a Ethernet breakout board ($2 at Sparkfun). This lets you use the Ethernet cables but you don't have to use a full TCP/IP protocol, instead you can just hook up data pins to the breakout board, use the Ethernet to connect them, and then have them talk using serial. I use this quite a bit to place one wire sensors further from the Arduino for a strong yet cheap connection.