A properly heat-treated steel can be stronger in both tensile and yield strength. The hardness and "brittleness" are factors to control, and different alloys respond quite differently.
For example, I ran across this a while back during a discussion of heat treat requirements for 4140 steel over at Practical Machinist. I found the information on embrittlement effects interesting, especially the fact that the notch toughness decreased in the midpoint tempering ranges (figure 2).
http://www.nhml.com/resources/2007/4...ment-of-steels
Some of you may find this discussion on bolt strength of value:
http://www.rockcrawler.com/techrepor...ners/index.asp
As far as sourcing metal, you can get 1144 Stressproof, 4130, 4140, or 4340 fairly inexpensively at places like
www.onlinemetals.com. I've seen some Grade 8 bolts specified with AISI 4037 or 4042.