$l_1$ minimization / compressed sensing comes to mind. Does anyone have any concrete examples? Or is such a construct completely useless?

1$\begingroup$ I'm pretty sure that a Hilbert space uses defines its "standard" norm in terms of the inner product. So, once you pick the inner product, you've fixed the norm as just the square root of <x,x>. Can you please clarify the question and maybe provide some background and motivation? $\endgroup$– Steve FlammiaNov 16, 2009 at 0:53

$\begingroup$ I'm not sure I understand. If you're using a different norm, what's its relationship to the Hilbert space structure? $\endgroup$– Qiaochu YuanNov 16, 2009 at 7:11
4 Answers
One place where this is used is with Hilbert bundles. Taking $L^2$functions on a space generally works very badly, so one instead takes $L^{2,1}$functions  functions which are differentiable (almost everywhere) with squareintegrable first derivative. However, the transition functions aren't isometries with respect to this norm so one does tend to use the $L^2$norm on this space, remembering that the fibres aren't complete with respect to the norm.
Another use is in Wiener integration. Depending on one's point of view, one either has a Hilbert space with a weaker norm, or a Banach space with a dense subspace equipped with a Hilbert norm. Essentially, having the two norms means that one can "tame" stuff with respect to one norm by using the stronger one.
This extends further to the notion of "rigged Hilbert spaces".
Generally, the idea is that you want to work in one space but you don't have enough control over convergence, so you introduce a stronger norm and then ordinary convergence with respect to the stronger norm implies fantastic convergence with respect to the weaker one.
(I apologise for using vague language, but the question doesn't give much indication of how deep an answer to give. For those who know a little about ideals of operators, one generally wants the inclusion from the strong norm to the weak to be at least trace class, and often HilbertSchmidt.)
suppe, have you heard of Banach spaces? They're a generalization of Hilbert spaces: they are complete normed vector spaces, but their norms need not arise from any inner product. $l\_1$ is just one example.
I'm sorry if you're already familiar with all that; your question has almost no context, so it's hard to answer appropriately. Your question is confusing because if you're in a "Hilbert space" using some strange norm, then you're really not in that Hilbert space; you're in another normed vector space (possibly a Banach space). You should think of the inner product and its associated norm as being an essential part of the definition of a Hilbert space.
Firstly, a Hilbert space is complete: the $l^1$norm is defined on a dense subspace of $l^2$ but not on the whole space. Secondly, if you can equip $l^2$ with another norm, then either this norm is incomplete or (by the closed graph theorem) it will be equivalent to the usual norm.
I think you might wish to try and make your question more limited, but more precise.
I don't think this is exactly what you are asking, but here's one thing that comes to mind. One could take the Hilbert space $H_0^1(\Omega)$ (the closure of $C_c^\infty(\Omega)$ in the Sobolev $H^1$ topology), where say $\Omega \subset \mathbb{R}^n$ is a bounded open set with smooth boundary. There are two equivalent inner products on this space. That is, if one defines
$$ \u\_1 := \int_\Omega (u^{2}+\nabla u^{2}) $$ and $$ \u\_2 := \int_\Omega \nabla u^{2} $$
Then by a Sobolov inequality (sometimes called Poincaré's inequality) we obtain two equivalent norms on $H^1_0(\Omega)$ arising from inner products − $\int_\Omega(uv+\nabla u\cdot\nabla v)$ and $\int_\Omega \nabla u\cdot\nabla v$ resp. This type of Sobolev inequality is used extensively by those studying PDEs. If you would like to learn more about this, 1) I'm sure wikipedia offers some basic resources, and 2) there is a decent introductory book by Evans (Partial Differential Equations)  chapter 5. I apologize if this is not what you were looking for and/or if you were already familiar with this.