You can surely do that! One of my test setups is Mega 2560 + W5100 Ethernet Shield (Made in China, but identical to the official one) + 2 boards similar to the $6,50 you have in stock, but without OptoCouplers + DS18B20 mounted on a protoboard. It works like a charm!
If you use pins 8, 7, 6 and 5 for the relays and pin 2 for the DS18B20 data line, it will most likely work out of the box!