Held keys in associations

1. Wrap the entire key in Hold, if you really want to keep things that might evaluate in the keys of an association (HoldPattern is a red herring: keys aren't patterns). Alternatively use ToString. But generally this just sounds like a dangerous and confusing game to play, to me. What exactly are you trying to do? There is probably a better way that doesn't involve using the keys of associations.

2. No, Map and AssociationMap shouldn't evaluate keys. Please report that behavior to tech support and it'll wend its way to Konstantin. If it's a simple fix it'll probably happen for 10.0.2, if it requires a big rewrite or a loss in efficiency it may take longer.

3. Keys have to remain unevaluated for associations to have any efficiency advantages over ordinary lists of rules. There's no way around that.

In 10.1.0 we have the new function KeyValueMap. You can use these functions, although they are not perfect

heldNormal[assoc_] := 
 Apply[Rule, Hold@Evaluate@KeyValueMap[Hold, assoc], {2}]
map[f_, assoc_] := 
 Association @@ 
  Unevaluated @@@ List@MapAt[f, heldNormal@assoc, {All, All, 2}]
associationMap[f_, assoc_] := 
 Association[ReleaseHold@Map[f, heldNormal[assoc], {2}]]

Example

With

testAssoc = Association[Unevaluated[{a -> b, c -> b}]];
b := (Print@#; #) &@"Fail";
a := (Print@#; #) &@"Boo";

We get

map[Hold, testAssoc]
associationMap[
 Function[Null, 
  Identity @@ RuleDelayed @@@ MapAt[Hold, Hold[#], {{1, 1}}], 
  HoldAll], testAssoc]

<|a->Hold[b],c->Hold[b]|>
<|Hold[a]:>b,Hold[c]:>b|>

Notes

Unfortunately heldNormal does not know whether to use Rule or RuleDelayed, which Normal does do. For this purpose, we could consider an alternative using something like the following snippet

Normal[Hold /@ KeyMap[Hold, testAssoc]]

Perhaps this answer can be extended with alternatives to other members of the *By family. See my answer here.