How to evaluate and compare the performance of algorithms in practice? Let $A$ be a heuristic algorithm for problem $Q$.
I want to evaluate the performance of my algorithm in a 
specific practical environment and
compare it to other algorithms.
Is there a rigorous framework for comparison of algorithms in practice?

One method to evaluate the performance and compare it with other algorithms
is to run them on randomly generated inputs from a distribution
(based on actual inputs or a theoretical model of inputs) and
measure the average running time of the algorithms.
However I want to be able to express that one algorithm is better than other one
in stronger sense than just having better expected running time.

What do people use for to express stronger conditions?
Would standard deviation be a useful for this purpose?
What is the best way to measure the confidence level of the performance? 

Are the any references (books/surveys/tutorials/...) on how to compare the performance of algorithms in practice?
I believe what you're looking for is the field of Experimental Algorithmics. There is a text by McGeoch, an ACM Journal, and a previous question on this site that provides a reading list for the field.