I have completely no idea where to begin, what tools to use, nothing.

Godlike modders from SEN, please help ; )

Use either SCAI Edit or PyAI. As for a tutorial, google one. I'm not expert enough at it to help.

Use PyAI and open up the default scripts. The best ones to look at are the Expansion Custom Level scripts for the three races. Broodwarai.com has good resources for AI editing.

Here is a list of commands: http://www.broodwarai.com/forums/index.php?showtopic=11