The best solution is to use a UIViewController instead of a UITableViewController. (This has been said above, but let me give you the details).
Create a new UIViewController with it's respective XIB. Inside your new UIViewController's view drag in a UITableView, resize it, and drag your UIToolbar wherever you want.
You should have something like this:
The black border represents the UIViewController's main view. The red border represents the table view. The blue border represents your toolbar.
Afterwards, make your UIViewController comply with two protocols: UITableViewDelegate and UITableViewDataSource. You will manually have to implement it's essential methods such us cellForRowAtIndexPath, numberOfRowsInSection, etc, but it shouldn't take you long.
Link your UITableView to your UIViewController. Link it's "data source" and "delegate" properties to the view controller as well.
You will have your setup ready in less than 15 minutes.