I see that you are new and that you are from Australia, but you offer very little info about yourselves.
Starting the Northern Tier route in Maine in mid-April isn't exactly a great idea.
If you were from Russia, Canada, even the South Island - then maybe.
The average High and Low are 10/0 C in the lower elevations - colder in the mountains.
There is a good chance of snow - plus cold rain every third day.
Not to mention that most facilities do no open until mid May or later.
In the Australian bush, if you get soaked in a storm, you can dry out quickly the next day.
Not so if you have a week of steady, cold drizzle in northern New England.
Even if it is "doable" you are likely to be miserable.
Granted, you might hit a warm, dry spell just perfectly - but not likely.
I would strongly recommend starting significantly further south in mid-April -
Then work your way diagonally north.
As for free camping -
On almost all National Forest (USFS) and Bureau of Land Management (BLM) lands -
You can camp for free for up to 14 days as long as you are 1/4 to 1/2 mile from developed sites. (varies)
These are federal lands comparable to Crown Lands in Australia. Fire restrictions are likely to apply.
Random camping is NOT permitted in most National Parks (NPS) -
Although many offer free backcountry camping by permit, sometimes only a short distance from the road.
National Wildlife Areas and Refuges rarely offer any camping at all and huge fines for those who do.
State and local agencies offer fewer free camping options.
Some state forests offer free camping - also some state wildlife areas do.
Montana used to offer extensive free camping at Fishing Access Sites - but these have been reduced.
(I'm guessing cost and vandalism - plus liability issues. It's a modern world.)
Usually state sites a re small and require advance knowledge/research -
But some of them are quite lovely and out-of-the-way.
Here's a link to Montana's state sites - http://fwp.mt.gov/fishing/searchFas.html
Yellowstone River, Miles City