Erwägungen:
1. Mit Urteil vom 6. Februar 2008 wies die Beschwerdekammer des Obergerichts des Kantons Solothurn eine Beschwerde von X._ gegen die Ablehnung eines Ausstandsbegehrens durch den Oberstaatsanwalt des Kantons Solothurn unter Auflage der Verfahrenskosten von Fr. 530.-- ab. Ein Gesuch von X._ um Erlass dieser Gerichtskosten wies das Finanzdepartement des Kantons Solothurn ab. Seine dagegen gerichtete Beschwerde an das Verwaltungsgericht des Kantons Solothurn wurde ebenfalls abgewiesen, soweit darauf eingetreten werden konnte. Abgewiesen wurden ebenfalls alle Ablehnungs- und Ausstandsbegehren von X._ (angefochtenes Urteil E. 2c).
2. Mit Beschwerde "in öffentl. Angelegenheiten + Verfassungsbeschwerde" beantragt X._ dem Bundesgericht zunächst, es seien unabhängige Bundesrichter einzusetzen, die noch nie negativ gegen ihn entschieden hätten; Bundesrichter Schneider und Gerichtsschreiberin Hill müssten in den Ausstand treten.
Dieses Gesuch wird mit der Bezeichnung der unterzeichnenden Gerichtspersonen gegenstandslos, da diese bisher nicht mit der Beurteilung von Rechtsmitteln des Beschwerdeführers befasst waren.
3. Auf die nach Ablauf der Beschwerdefrist (6. Juli 2009) eingereichte Beschwerdeergänzung vom 7. Juli 2009 ist nicht einzutreten.
4. 4.1 Der Beschwerdeführer beantragt sodann die Aufhebung des angefochtenen Entscheides wegen Verletzung zahlreicher Bestimmungen der Bundesverfassung und der EMRK; namentlich macht er geltend eine Verletzung des Rechts auf ein faires Verfahren, die Verletzung der persönlichen Freiheit sowie der Wirtschafts- und Berufswahlfreiheit sowie Willkür "usw. usw. usw".
4.2 Die Beschwerde in öffentlich-rechtlichen Angelegenheiten ist unzulässig gegen "Entscheide über die Stundung und den Erlass von Abgaben" (<ref-law>). Der angefochtene Entscheid betrifft eine Verfügung über den Erlass von Gerichtskosten und fällt damit unter den Ausschlussgrund (Urteil 2C_261/2009 vom 14. Mai 2009 E. 3.1), weshalb die Beschwerde in öffentlich-rechtlichen Angelegenheiten hier nicht zulässig ist.
4.3 Der angefochtene Entscheid erging gestützt auf § 14 Abs. 1 des solothurnischen Gebührentarifs vom 24. Oktober 1979 (GT/SO). Diese Bestimmung räumt dem Betroffenen keinen Rechtsanspruch ein, weshalb kein rechtlich geschütztes Interesse zur Geltendmachung einer Verletzung des Willkürverbots im Rahmen der subsidiären Verfassungsbeschwerde besteht ( Urteil 2C_261/2009 vom 14. Mai 2009 E. 3.2).
5. 5.1 Trotz fehlender Legitimation zur Geltendmachung der Verletzung des Willkürverbots ist es zulässig, mit subsidiärer Verfassungsbeschwerde die Verletzung von Parteirechten zu rügen, deren Missachtung auf eine formelle Rechtsverweigerung hinausläuft. Das rechtlich geschützte Interesse ergibt sich diesfalls aus der Berechtigung der Partei, am Verfahren teilzunehmen und ihre Parteirechte auszuüben (vgl. <ref-ruling> E. 6.2 S. 198). Allerdings setzen entsprechende Verfassungsrügen im Rahmen der Beschwerdebegründung eine genügende Substantiierung im Sinne von Art. 106 Abs. 2 in Verbindung mit <ref-law> voraus.
5.2 Soweit der Beschwerdeführer geltend macht, die Vorinstanz hätte in einem separaten Entscheid zunächst über sein Ausstandsbegehren entscheiden müssen, nennt er keine Bestimmung des kantonalen Rechts, die eine solche separate Beurteilung verlangt. Es zeigt auch nicht auf, inwiefern sich dies aus dem Anspruch auf rechtliches Gehör oder aus demjenigen auf ein faires Verfahren (Art. 6 Ziff. 1 EMRK bzw. <ref-law>) ergeben könnte. Dem Beschwerdeführer ist dadurch ohnehin kein Rechtsnachteil erwachsen, da bei Gutheissung der Beschwerde gegen die Ablehnung des Ausstandsbegehrens auch der in der entsprechenden Besetzung getroffene materielle Entscheid schon aus formellen Gründen ohne weiteres aufgehoben würde.
Was den Vorwurf der Befangenheit betrifft, so lässt allein die Tatsache, dass solothurnische Richter gegen den Beschwerdeführer entschieden haben sollen, diese nicht als befangen erscheinen.
Dass und inwiefern gegen die Gerichtspersonen, die am angefochtenen Entscheid mitgewirkt haben, Ablehnungs- bzw. Ausstandsgründe bestehen, legt der Beschwerdeführer nicht in einer den Begründungsanforderungen genügenden Weise dar. Auf die entsprechenden, nur schwer verständlichen Vorbringen - einschliesslich den Antrag auf Einsetzung ausserkantonaler Richter bzw. eines Schiedsgerichts - ist daher nicht einzutreten.
6. Das Begehren des Beschwerdeführers auf Leistung einer Genugtuung ist nicht näher begründet, weshalb darauf nicht einzutreten ist.
7. Die Beschwerde ist offensichtlich unzulässig und im vereinfachten Verfahren nach <ref-law> zu erledigen. Der Beizug weiterer Akten erübrigt sich damit. Die Einholung der Vernehmlassungen der beteiligten Behörden erweist sich nicht als notwendig. Mit dem Entscheid über die Beschwerde wird auch das Gesuch um Erteilung der aufschiebenden Wirkung der Beschwerde gegenstandslos.
8. Die Gerichtskosten (<ref-law>) sind dem Beschwerdeführer aufzuerlegen, da er unterliegt (<ref-law>). Die unentgeltliche Rechtspflege setzt voraus, dass das Rechtsbegehren nicht aussichtslos erscheint (<ref-law>). Eine überhaupt nicht oder ungenügend substantiierte Beschwerde erscheint von vornherein als aussichtslos, weshalb für das bundesgerichtliche Verfahren die unentgeltliche Rechtspflege nicht gewährt werden kann.

Demnach erkennt das Bundesgericht:
1. Das Ausstandsgesuch wird infolge Gegenstandslosigkeit abgeschrieben.
2. Auf die Beschwerde wird nicht eingetreten.
3. Das Gesuch um unentgeltliche Rechtspflege wird abgewiesen.
4. Die Gerichtskosten von Fr. 300.-- werden dem Beschwerdeführer auferlegt.
5. Dieses Urteil wird den Parteien und dem Verwaltungsgericht des Kantons Solothurn schriftlich mitgeteilt.
Lausanne, 30. Juli 2009
Im Namen der II. öffentlich-rechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Einzelrichter: Der Gerichtsschreiber:
Karlen Küng