Aley is a German name (also apparently English), and the rumor you mention about the name being "changed at Ellis Island" is a myth. The manifests for ship passengers were made in Europe and names were taken directly from the immigrant before boarding the ship. If the name was changed at all, then it would have been changed at the port of departure by the immigrant, not at Ellis Island (or Castle Garden, before 1892). Here are some articles dispelling the "Ellis Island" myth.
According to the 1910 Census for Muskegon, MI, William Aley was born in Germany ca. April 1830, arrived in the U.S. in 1848 (at which time Ellis Island Immigrantion Station did not even exist) and William had been married to Caroline (Fass) for approximately 45 years (ca. 1855). I cannot find the manifest listing William (or Wilhelm) Aley in NY, but there were several ports at which he could have entered the US.
Freddie Aley is listed in the 1870 Muskegon MI Census with parents William and Caroline where the family name is mistranscribed online as "Alez", but you probably know this since you mentioned Prussia in your posting.
The birthplace is also tricky, since Germany didn't exist as a unified nation until 1871, so it's harder to determine just where a German immigrant born before 1871 might have originated. Prussia was a sprawling territory covering parts of modern (northern) Germany and Poland with other smaller "nations" (duchies, counties, etc, all independent of Prussia) in between.
Your Fred Aley was born in White River, Muskegon, MI according to his 1899 marriage register entry. Edna Gillet(e?)was born in Muskegon, MI. He and Edna were married in Tomahawk, Lincoln County, WI on 28 Jun 1899. The marriage entry lists William and Caroline Aley as parents of Fred.
I hope this is helpful to you and other researchers.