Arduino and 3W LED sharing the same power source, is it possible and how?
Specifications of the LED:
  Max. Current : 750 mA
  Forward voltage : 3.5 - 4.5 V Max.
  Working temperature: 60 °C


These specs are not good for a battery powered LED. 

3.5 - 4.5 Vf says it is a horribly inefficient LED.  

When battery powered, always start with an LED with the highest efficacy possible.  Today that LED is a Cree XP-G3 XPGDWT-01-0000-00ME3. High efficacy means more light and less heat.  This White, 5000K Cree LED has a efficacy of 180 lm/W. 

At 750 mA this LED's Vf is 2.85V. See Pg. 18 of datasheet. 


  Just using a resistance setup to regulate current to the LED, I know
  it's not very efficient


This is not always true. You can easily power this with the Arduino UNO's 3.3V. You cannot do this with a 3.5-4.5V LED. With a 2.85V LED powered by 3.3V with a current limiting resistor would give you an efficiency of over 86% no matter what current you run at. 


  I'm powering the Arduino with a USB cable and the LED with 4x AA NiMh batteries


Powering a 5V Arduino with 4.5V batteries is not good.  The Arduino wants at least a 5.1V input.  The Arduino Vin is run through a 5V NCP1117ST50T3G LDO regulator.  The minimum input voltage for the 5V NCP1117 is 4.950V.

You should just use a 5V USB power bank to power the Arduino and use the Arduino's 3.3V to power the LED. You probably cannot run it at more than 250-300 mA without a heatsink.  At 250 mA the Cree Vf is 2.7V so a 2-2.4 Ω half watt resistor would give you better than 80% efficiency.  Well, minus the the efficiency of Arduino's 5V and 3.3V LDOs.