--- Quote Start ---
...is it really that hard to make a Ethernet connection without NIOS :s
--- Quote End ---
If you are using a PHY chip such as National's DP83848, you can set up the basic operational modes using pin configurations. The data sheet for the PHY will explain this. When configured for Auto-negotiate mode the PHY will establish an ethernet connection automatically and enable you to transfer raw data in nibble-wide format - all without software intervention. If you want anything more sophisticated than this, such as a TCP/IP stack, your best solution would be using a Nios II rather than VHDL.
It can be a steep learning curve to implement a Nios II, but when you consider setting up TX/RX buffers, packet processing, and all else required for an IP stack, a VHDL solution would be quite a challenge, too.