It would make life simpler if you showed us a code sample of what you have tried. I can give you an idea of how I have done something almost exactly like this in the past but it may sound vague and may not fit your needs.
I've done this completely using the CGI module and HTML::Table. The key thing to remember is that your form should completely enclose the table. Each row of the table may have one or more hidden fields (possibly to identify the row number). The option to select all/deselect all was done in javascript, if I remember right.
See this is vague. If you can show code with minimal example of what you are trying to do, we will certainly help you figure out a great way to tackle your problem.
