My program needs to run at the maximum speed the Arduino can provide and I'm now in the need of a high precision timing function. The built-in micros() is only accurate for microseconds, but I'd like to measure as precise as a single instruction.
I've looked at the source code of the built-in timing stuff, but I can't figure out how to adjust it for more precision. It would be awesome if you could provide me with some code do do this.
You should read the data sheet - especially the bits about the hardware timers, and the input compare functionality.
sometimes refactoring the code or differetn approaches can give quite a speed up.
If you post you critical code (preferably a running sketch), we can try to optimize it - make a contest 
I think you need external hardware to measure that precisely.
You can set a fuse to output the system clock on PortB-0, 62.5nS.
Run that thru an 2-input AND gate, with your to-be-measured signal as the other input.
Use the hardware counters to count how many occurrences of clock come out while your signal is high.
Another way to get exact measurements is to call a piece of code 1000 times and then call the micros.
Ultimately you can use avrObjDump.exe(?) to generate the assembly listing and just count the instructions.