rcollyer's method looks great but for a reason I have yet to determine it fails in Mathematica 7. Here is a variation that does not.
Block[{$MessagePrePrint},
$MessagePrePrint := Row@{#, " at i = ", i} ~ToString~ StandardForm &;
Do[i^0, {i, -1, 1}]
]
This may not be ideal however, as every field in the message gets this tag. For example, if you enter the spurious Inner[f, {{1, 2}}, {3}] you get:
Inner::incom: Length 2 at i = 1 of dimension 2 at i = 1 in {{1,2}} at i = 1 is incommensurate with length 1 at i = 1 of dimension 1 in {3} at i = 1. >>
Perhaps this is a more flexible and convenient form:
EDIT: Full rewrite to place the tag in the message itself
SetAttributes[withTaggedMsg, HoldAll]
withTaggedMsg[sym_] := Function[,
Internal`InheritedBlock[{MessagePacket},
Unprotect[MessagePacket];
MessagePacket[name__, BoxData[obj_, form_]] /; ! TrueQ[$tagMsg] :=
Block[{$tagMsg = True},
Identity@MessagePacket[name, BoxData[RowBox[{
ToBoxes @ Style[
Row[{"At iteration", HoldForm[sym], "=", sym, Spacer[5]}, " "],
Black],
obj}], form]]
];
#
], HoldAll]
Usage:
Do[i^0, {i, -1, 1}] // withTaggedMsg[i]

Note: this only works with variables that are either globally accessible or are scoped using Block. For example,
f[x_] := Message[f::brains, x]
f[5] // withTaggedMsg[x]
(* At iteration x = x f::brains: -- Message text not found -- (5) *)
Module[{x = 5},
Message[f::brains, x]
] // withTaggedMsg[x]
(* At iteration x = x f::brains: -- Message text not found -- (5) *)
With[{x = 5},
Message[f::brains, x]
] // withTaggedMsg[x]
(* At iteration x = x f::brains: -- Message text not found -- (5) *)
Block[{x = 5},
Message[f::brains, x]
] // withTaggedMsg[x]
(* At iteration x = 5 f::brains: -- Message text not found -- (5) *)
This means that any variable that is scoped using Block can be used to tag a message. So, loop variables from Do and Table are accessible via this method, in addition to any Block variable. This makes it indispensable as a debugging tool.