For vaccines aimed at eliciting neutralizing antibodies, which would bind to viral surface proteins (such as HIV envelope) and prevent the virus from entering cells, the vaccine has to be surface protein.  But for vaccines aimed at reducing the virus infection but not completely preventing viral entry into the first cell, there are many more options.  T-cell responses can be produced by vaccines that inject DNA or RNA into cells which then produce peptides that are presented on MHC.

So, in general, B-cell (antibody-inducing) vaccines tend to be structural proteins and T-cell response inducing vaccines can be targeting any viral protein including virus regulatory proteins.

http://www.its-innovation.com/technology/T-cell-vaccines/

http://perspectivesinmedicine.cshlp.org/content/1/1/a007252.full

What I would like to know is what you mean with non-structural protein. If you talk virology it is a protein that is not involved in the structure of the capsid. However, in biology in general there are also proteins that have non-structural parts (part of the protein contains helices etc. whereas another part does not). One can easily make vaccines against the structural part of such proteins.

If they contain T cell epitopes you can do.

In principal you can induce a humoral immune response against any peptide epitope, if you combine it with a potent T-Helper cell epitope. The question of efficiency is difficult to answer and depends on where the protein is located.

Depends on what the vaccine is against.

For viral vaccines, the target is typically a conserved surface protein, usually one required for binding to the target cell, as noted by Brian above.

For bacteria, there are a wide variety of targets. Some vaccines can use anything on the cell surface (even some of the polysaccharide components of the cell wall) to trigger T-cell clearance of the bacteria and/or antibody-mediated serum bactericidal activity. Some bacteria secrete toxins (anthrax, tetanus, diphtheria, etc.), and the vaccine target is actually the toxin to generate neutralizing antibodies. Once the toxin is neutralized, these bacteria are easily cleared by the normal immune response. Some bacteria have specific virulence factors that must be targeted.

The criteria isn't really that the target should be structural, but that it should be well conserved (to prevent escape mutations), it should be exposed to the immune system (so not something that remains internal to the virus or bacterium), and that the immune response to that target (T-cell or antibody) should effectively stop the infection. How that works varies depending on the organism you are targeting. The last one is what makes it so hard - antibodies to some targets don't do anything to stop the infection, and pathogens have evolved lots of ways to trick the immune system into attacking the wrong target.