Leonid provides a nice method for doing this within "pure functions" but I think it should be pointed out that the common method for doing this is pattern matching.

**I argue that destructuring is the *foundational use* of pattern matching in *Mathematica*.**

Every replacement pattern, be it an explicit rule (`:>`, `->`) or part of definition (`:=`, `=`) that uses a named pattern on the left-hand side that does not match the entire expression or argument is doing destructuring.

Applied to your specific example:

 f[a_, {i_, j_}] := a == 0 || Abs[i - j] <= 1

 triDiagonalQ[mat_] := And @@ Flatten @ MapIndexed[f, mat, {2}]

Or:

 triDiagonalQ[mat_] := And @@ Flatten @
 MapIndexed[#2 /. {i_, j_} :> # == 0 || Abs[i - j] <= 1 &, mat, {2}]

The second example is almost exactly what you asked for: "with a `{i, j} <- #2` somewhere" 
It's just turned around: `#2 /. {i_, j_}`.

This destructuring is common in *Mathematica* programming for experienced users.

Among many examples:

[Here][1] I use it with to separate `a + b + c`:

 (a + b + c) /. head_[body___] :> {head, body} (* Out= {Plus, a, b, c} *)

[Here][2] Leonid uses it in a recursive function. (`{x_, y_List}`)

Szabolcs uses it in [`iter`][3], also recursive.

Heike uses it with `/.` in [`PerforatePolygons`][4] and with `:=` in [`torn`][5].

[Here][7] I used it simply in `formula` but also in `MakeBoxes[defer[args__], fmt_] :=` where the parameter pattern `defer[args__]` serves to match the literal head `defer` while also destructuring.

In [`withOptions`][8] it is used both in the function definition and in the replacement rule.

I also used it in [`inside`][9], [`withTaggedMsg`][10], [`pwSplit`][6], etc.

----------

Another, simpler form of destructuring exists in the form of `Set` and `List` (`{}`). A matching `List` structure on the left and right sides of `=` will assign values part-wise.

 {{a, b}, c, {d}} = {{1, 2}, 3, {4}};
 
 {a, b, c, d}

> {1, 2, 3, 4}

This is used e.g. in the first [`LUDecomposition`][11] example, and R.M uses it [here][12].

 [1]: http://mathematica.stackexchange.com/a/2450/121
 [2]: http://mathematica.stackexchange.com/a/5756/121
 [3]: http://mathematica.stackexchange.com/a/1328/121
 [4]: http://mathematica.stackexchange.com/a/5891/121
 [5]: http://mathematica.stackexchange.com/a/4155/121
 [6]: http://mathematica.stackexchange.com/a/1129/121
 [7]: http://mathematica.stackexchange.com/a/7882/121
 [8]: http://mathematica.stackexchange.com/a/3259/121
 [9]: http://mathematica.stackexchange.com/a/9410/121
 [10]: http://mathematica.stackexchange.com/a/8219/121
 [11]: http://reference.wolfram.com/mathematica/ref/LUDecomposition.html
 [12]: http://mathematica.stackexchange.com/a/4027/121