There is BLM land on pretty much all sides of the park that is legal to camp on.
Check this (shitty) map: nationalatlas.gov/mapmaker?...;left=-1146235.49251497&right=-1106598.59131737&top=-217193.652694611&bottom=-245064.652694611&mWidth=950&mHeight=668&LonLat=-113.6336192%2C42.1001924%2CAlmo&visLayers=grid,federallands,states,roads,citiestowns,wa&visCats=CAT-ref,CAT-boundary,CAT-trans
The dark green blob is the city, the yellow is BLM land.
Edit: Much better map on caltopo: http://caltopo.com/map.html#ll=42.09257,-113.70202&z=13&b=t&o=f,r&n=1,0.25&a=sma