In Cura (and Slic3r), you can 100% customize what the printer does before printing your actual model through custom start/end g-code.

If you navigate to the Start/End-GCode tab in Cura, then select start.gcode, you can see what operations are run before each print begins. Lines prefixed with ; are comments, and does not affect the printing in any way.

Basically, we want to manually tell the printer to do the auto leveling before heating up the nozzle by editing the g-code in start.gcode.

G-Code generated with the default start.gcode:

If you try to slice some model with the default code found in start.gcode, you will get something like the following (depending on your printer):

; CURA AUTOMATICALLY INSERTS THESE TEMPERATURE CODES

M190 S70.000000 ; Set bed temperature to 70 degrees
M109 S210.000000 ; Set nozzle temperature to 210 degrees


; THESE ARE THE CODES FROM START.GCODE (for a ROBO 3D R1) 

G28          ;move printer to endstops (the home position)
G92 E0       ;zero the extruded filament length
M565 Z-1     ;set z-probe offset
G1 Z5 F5000  ;move the printer 5mm above the bed
G29          ;run auto-leveling


; THE ACTUAL MODEL BEGINS HERE

;Layer count: 168
;LAYER:0
.
.

Analyzing the g-code output

At the top of this code snippet, we can see that Cura automatically inserts g-code for heating up the bed and nozzle to their respective temperatures with the M190 and M109 g-codes. This means the printer always will heat up the nozzle before reading the start.gcodes that we set. However, if we manually override M109 code in start.gcode, the M109 at the top will automagically disappear from the generated g-code output! (Thanks, @TomvanderZanden!)

We could therefore use the auto-leveling command G29 before manually setting the nozzle temperature with M109; specifically, we want to add M109 S{print_temperature}, which reads the Basic -> Print Temperature-setting in Cura, and replace {print_temperature} with it automatically.

Manipulating start.gcode:

In order to postpone heating the hotend till after probing, start.gcode could be something like:

G28          ;move printer to endstops (the home position)
G92 E0       ;zero the extruded filament length
M565 Z-1     ;set z-probe offset     <-----   ( YOU HAVE TO ADJUST THIS, READ BELOW)
G1 Z5 F5000  ;move the printer 5mm above the bed
G29          ;run auto-leveling
M109 S{print_temperature}    ;set nozzle temperature, and wait for it heat up

And that's about it! You can then use these codes in your start.gcode. However, you probably will have to recalibrate your z-prove offset.

Adjust z-probe offset:

Normally, auto-leveling is done with the nozzle heated for a reason: when the nozzle is warm, it expands slightly, moving closer to the bed. You might therefore have to adjust your Z-probe offset with the M565 command (as demonstrated in the snippet) to account for the increase in nozzle length when warm.

Remember:

Remember that when editing g-code in this manner, you will take full control of how the printer operates. You could therefore very well do something unintended, so keep the power switch close!