Not to try and prove you all wrong or anything, but I found this article a while ago which says that it is possible to separate the declarations and definitions for template functions into .h and .cpp files. It does seem though (from the sample compiler/linker messages he provides) that he's using MSVC rather than GCC.
I use templates in some of my projects and have been using "Method 1" (or as he writes, "Mehtod 1") to get around linking errors. Although, I too use only MSVC (haven't gotten a chance to learn how to use GNU tools yet).
EDIT: Fixed typo.