Na, ich würde es erst einmal mit einem Brief an das Büro des Premierministers und des Justizministers versuchen, die können einen Staatsbürger aus der Staatsbürgerschaft entlassen (allerdings sind Deine Kinder dann nach wie vor noch Staatsbürger).

Ein Rechtsanwalt kann Dir da eh' nicht weiterhelfen, Du bist da sozusagen auf das Entgegenkommen Deines (Zweit)Vaterlandes angewiesen. Es gibt in Tunesien zwar ein Recht darauf, daß ein Staatsbürger das Land betreten kann, aber kein Recht darauf, daß ein Staatsbürger seine Staatsbürgerschaft aufgeben kann.

Das ist halt eine der Kehrseiten binationaler Beziehungen, an die man zunächst gar nicht denkt...